程序设计实践4w-有限自动机课件

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