《程序设计实践4w有限自动机.ppt》由会员分享，可在线阅读，更多相关《程序设计实践4w有限自动机.ppt（30页珍藏版）》请在三一办公上搜索。
1、1,2,前言,输入一个字符串，判断其是否是合法的C语言标识符；输入一个字符串，判断其是否是 形式(即先输入a、再输入b、最后输入c，且输入的a、b、c的个数相同）；。针对类似的字符串识别问题，建立有限状态自动机模型，可以为分析、求解带来很大的帮助。,3,6.1 基本概念,例1：打电话(自动机在通信领域的应用)。在一次呼叫中，从建立连接到通话完毕，要经历摘机，拨号，应答，进行通话等过程，话机的状态及状态迁移如下所示。,状态迁移,状态,4,6.1 基本概念,例2：串口通信 两台微机通过串口通信,需在两台机器间建立好连接后，才可以传递数据，可以使用有限状态自动机，描述串口通信的状态。,q0：空闲状态
2、q1:等待应答状态q2：通信状态,5,电话和串口都可抽象为有限自动机 1.对象处于某一相对稳定的状态下；2.某个事件（输入）发生；3.这一事件引起一串处理发生，包括执行特定 的功能，产生相应的输出等；4.处理结束，对象迁移到一个新的相对稳定状态。,6.1 基本概念,6,6.1 基本概念,什么是有限状态自动机？是一种具有离散输入/输出系统的数学模型，简称 有限自动机。这一系统具有任意有限数量的内部“状态”。状态：一个标识，能区分自动机在不同时刻的状况。有限状态系统具有任意有限数目的内部“状态”自动机接受一定的输入，执行一定的动作，产生一定的结果。,7,6.1 基本概念,自动机的本质：根据状态、输
3、入和规则决定下一个状态状态 输入（激励）规则 状态迁移可能的状态、运行的规则都是事先确定的。一旦开始运行，就按照事先确定的规则工作，因此叫“自动机”。使用状态迁移描述整个工作过程。大量通信软件的基本工作机制都是有限状态自动机。自动机理论在通信领域中的应用极为广泛,8,有限自动机示意图,工作原理：读头在输入带上从左向右移动，每当读头从带上读到一个字符时，便引起控制器状态的改变，同时读头右移一个符号的位置。,组成 一个有限控制器 一个读头 一条写有字符的输入带,6.1 基本概念,9,控制器包括有限个状态，状态与状态之间存在着某种转换关系。每当在某一状态下读入一个字符时，便使状态发生改变（称为状态转
4、换）。状态转换包括以下几种情况：1)转换到其自身，即保持当前状态不变；2)转换的后继状态只有一个；3)转换的后继状态有若干个。如果一个有限自动机每次转换的后继状态都是唯一的，称为确定的有限自动机（DFA）；如果转换的后继状态不是唯一的，则称为不确定的有限自动机（NFA）。通常把有限自动机开始工作的状态称为“初始状态”，把结束工作的状态称为“终止状态”或“接受状态”。,6.1 基本概念,10,确定的有限自动机的形式化定义确定的有限自动机是一个五元组其中：有限的状态集合；：有限的输入字母表；：转换函数，是 到 的映射；：初始状态，；：终止状态集，；,6.1 基本概念,（初始状态只有一个）,11,为
5、了描述一个有限自动机的工作状况，可采用状态转换图。状态转换图是一个有向图，图中的每个节点表示一种状态，一条边（或弧）表示一个转换关系。,初始状态：q0终止状态：q3控制器的状态集合：q0,q1,q2,q3,6.1 基本概念,a,12,有限自动机的状态转换图,q0,q1,q3,q2,a,a,b,b,a,b,状态集合字母表初始状态终止状态集,转换函数,用于识别输入的字符串是否是 或者 形式的有限自动机。,13,存储程序的计算机本身也可以认为是一个有限状态机。输入输出都是离散量，某时刻的状态由当时进行的操作、寄存器、主存储器和辅助存储器中存储内容确定。一个运行中的程序在不同时刻也具有不同的状态，程序
6、执行中的状态就是各种“变量”当时所存放的值。比如我们设计的求5！的程序，初始进入循环前的状态是：(p=1 and i=2),执行完循环后的状态是：（p=40 and i=6）。,6.1 基本概念,14,6.2 程序设计实例研究,应用有限自动机模型求解问题的核心问题就是抽象出状态，描述出状态转移图和状态转移函数应用有限自动机解题步骤1、确定输入集2、绘制状态迁移图（确定状态，在每一个状态下对输入进行分类，确定下一个状态）3、确定状态转移函数（在某状态下，接收到某一字符后，自动机要执行的操作，以及迁移到的下一状态）,15,设计交通车辆观测统计算法。问题描述：在一个路口设置一个探测器，通过通信线路连
7、接到后台的计算机。路口每通过一辆汽车，探测器向计算机发出一个车辆信号1，探测器每隔1秒钟向计算机发出一个时钟信号0，观测结束向计算机发出结束信号。要求在计算机上设计一个程序，能够接收探测器发出的信号，统计出观测的时长、在观测时长内通过的车辆总数、以及两辆车之间最大的时间间隔。,问题分析：探测器向计算机发出的信号可以认为是一个任意长的字符序列（以EOF结束），比如：“，这样设计程序实际上演变为读取该字符序列，然后进行相关的操作。,1,观测时长：字符序列中0的个数(6秒)；车辆总数：字符序列中1的个数(9辆)；两车间最大时间间隔：两个1之间的最大连续0的个数(3秒)；,6.2 程序设计实例研究,1
8、6,重新审题：我们所设计的程序就是读入以EOF结束的由0或者1组成的字符串，这个字符串可以映射为有限自动机模型中的字符输入带，我们的任务就是设计控制器程序逐字符地读取输入带，进行处理并引起控制器的状态改变，最终产生输出，因此这个问题的求解就抽象为一个有限自动机。,6.2 程序设计实例研究,17,交通灯观测实例研究-解法1,1、确定输入集T1，0，EOF 2、每接收一类输入都认为进入一个固定状态，加上初始状态，共4个状态 q0：初始状态 q1：接收到1后的状态 q2：接收到0后的状态 q3：接收到EOF后的终止状态3、绘制状态迁移图，确定状态转换函数（每一个状态下对输入集进行分类，确定转换函数）
9、,18,3、确定转换函数当前状态是q0(state=q0)：读入1：vehicles+;state=q1读入0：seconds+;state=q2读入EOF：state=q3当前状态是q1(state=q1)：读入1：vehicles+;读入0：interval=1;seconds+;state=q2读入EOF：state=q3,19,当前状态是q2(state=q2)：读入1：if(vehicles0)处理最大时长 vehicles+;state=q1读入0：seconds+;if(vehicles0)interval+;读入EOF：state=q3终止状态集F=q3,20,有限自动机解题通
10、用处理模式,解法2对应代码：解法1对应代码：,此处自动机会有不同处理,21,交通灯观测实例研究-解法2,1、确定输入集T1，0，#2、对解法1的输入集状态，按照接收输入后可能出现的不同“动作”进行细分，确定细分状态:输入0后的状态细分此前从未出现1：若接收到这样的0,则系统进入状态 q1此前出现过1：若接收到这样的0,则系统进入状态 q2输入1后的状态细分这是第一个1：进入状态 q3这不是第一个1，且前面是0：进入状态 q4这不是第一个1，且前面是1:进入状态 q5#进入结束状态 q6,22,交通灯观测实例研究-解法2,3、绘制状态迁移图,说明：在q0q5的任何一个状态下，如果接收到字符#,则
11、进入终止状态q6。此处为了保持图的简洁，没有画出到q6的迁移。,23,交通灯观测实例研究-解法2,4、确定状态转移函数当前状态是q0读入1：vehicles+;state=q3读入0：seconds+;state=q1读入#：state=q6当前状态是q1读入1：vehicles+;state=q3读入0：seconds+;读入#：state=q6,24,交通灯观测实例研究-解法2,4、确定状态转移函数（续）当前状态是q3读入1：vehicles+;state=q5读入0：seconds+;interval+;state=q2读入#：state=q6当前状态是q5读入1：vehicles+;读
12、入0：seconds+;interval+;state=q2读入#：state=q6,25,交通灯观测实例研究-解法2,4、确定状态转移函数（续）当前状态是q2读入1：vehicles+；if(intervallongest)longest=interval;interval=0;state=q4读入0：seconds+;interval+;读入#：state=q6当前状态是q4读入1：vehicles+;state=q5读入0：seconds+;interval+;state=q2读入#：state=q6,26,6.2 程序设计实例研究,例2 检验输入是否是合法的C语言注释/*/,q1:等待
13、*状态q2：注释开始状态q3:等待/以结束注释状态q4：已接收注释结束状态,27,6.2 程序设计实例研究,转换函数分析start状态下：输入/:state=q1输出非/:state=ERRORq1状态下：输入*:state=q2输出非*:state=ERRORq2状态下：输入*:state=q3输入EOF：state=ERROR输出其他:state=q2,28,6.2 程序设计实例研究,转换函数分析(续）q3状态下：输入*:状态不变输入/:state=q4输入EOF：state=ERROR输出其他:state=q2q4状态下：输入EOF：state=ACCEPT输出其他:state=ERROR,29,6.2 程序设计实例研究,例3 去除C语言注释,30,
