1、导论第导论第10章章 有限状态自动机有限状态自动机前言前言 输入一个字符串，判断其是否是合法的输入一个字符串，判断其是否是合法的C C语言语言标识符；标识符；输入一个字符串，判断其是否是输入一个字符串，判断其是否是 形式形式(即先输入即先输入a a、再输入、再输入b b、最后输入、最后输入c c，且输，且输入的入的a a、b b、c c的个数相同）；的个数相同）；。针对类似的字符串识别问题，建立有限状态自针对类似的字符串识别问题，建立有限状态自动机模型，可以为分析、求解带来很大的帮助动机模型，可以为分析、求解带来很大的帮助。nnncba6.1 6.1 基本概念基本概念例例1 1：打电话：打电话
2、(自动机在通信领域的应用自动机在通信领域的应用)。在一次呼叫中，从建立连接到通话完毕，要在一次呼叫中，从建立连接到通话完毕，要经历摘机，拨号，应答，进行通话等过程，话机的经历摘机，拨号，应答，进行通话等过程，话机的状态及状态迁移如下所示。状态及状态迁移如下所示。q0q0q1q1q2q2q3q3q4q4摘机摘机收到拨号音收到拨号音拨号拨号收应答信号收应答信号挂机挂机收齐号码收齐号码q0:q0:空闲状态空闲状态q1:q1:等待拨号音状态等待拨号音状态q2:q2:可以拨号状态可以拨号状态q3:q3:等待应答状态等待应答状态q4:q4:通话状态通话状态状态迁移状态迁移状态状态6.1 6.1 基本概念基
3、本概念例例2 2：串口通信：串口通信 两台微机通过串口通信两台微机通过串口通信,需在两台机需在两台机器间建立好连接后，才可以传递数据，可以使用有器间建立好连接后，才可以传递数据，可以使用有限状态自动机，描述串口通信的状态。限状态自动机，描述串口通信的状态。传输数据传输数据收到收到应答应答断开断开连接连接发出连接请求发出连接请求q0q1q2q0q0：空闲状态：空闲状态q1:q1:等待应答状态等待应答状态q2q2：通信状态：通信状态 电话和串口都可抽象为有限自动机电话和串口都可抽象为有限自动机 1.1.对象处于某一相对稳定的状态下；对象处于某一相对稳定的状态下；2.2.某个事件（输入）发生；某个事
4、件（输入）发生；3.3.这一事件引起一串处理发生，包括执行特这一事件引起一串处理发生，包括执行特定定 的功能，产生相应的输出等；的功能，产生相应的输出等；4.4.处理结束，对象迁移到一个新的相对稳定状处理结束，对象迁移到一个新的相对稳定状态。态。6.1 6.1 基本概念基本概念6.1 6.1 基本概念基本概念l什么是有限状态自动机？什么是有限状态自动机？是一种具有离散输入是一种具有离散输入/输出系统的数学模输出系统的数学模型，简称型，简称 有限自动机。这一系统具有任有限自动机。这一系统具有任意有限数量的内部意有限数量的内部“状态状态”。状态状态：一个标识，能区分自动机在不同时一个标识，能区分自
5、动机在不同时刻的状况。有限状态系统具有任意有限数目刻的状况。有限状态系统具有任意有限数目的内部的内部“状态状态”自动机接受一定的输入，执行一定的动自动机接受一定的输入，执行一定的动作，产生一定的结果。作，产生一定的结果。6.1 6.1 基本概念基本概念 自动机的本质自动机的本质：根据状态、输入和规则决定下：根据状态、输入和规则决定下一个状态一个状态状态状态 输入（激励）输入（激励）规则规则 状态迁移状态迁移 可能的状态、运行的规则都是事先确定的。一可能的状态、运行的规则都是事先确定的。一旦开始运行，就按照事先确定的规则工作，因旦开始运行，就按照事先确定的规则工作，因此叫此叫“自动机自动机”。使
6、用状态迁移描述整个工作。使用状态迁移描述整个工作过程。过程。大量通信软件的基本工作机制都是有限状态自大量通信软件的基本工作机制都是有限状态自动机。自动机理论在通信领域中的应用极为广动机。自动机理论在通信领域中的应用极为广泛泛有限自动机示意图有限自动机示意图工作原理：读头在输入带上从左向右移动，每当读工作原理：读头在输入带上从左向右移动，每当读头从带上读到一个字符时，便引起控制器状态的改头从带上读到一个字符时，便引起控制器状态的改变，同时读头右移一个符号的位置。变，同时读头右移一个符号的位置。组成组成 一个有限控制器一个有限控制器 一个读头一个读头 一条写有字符的输入带一条写有字符的输入带6.1
7、 6.1 基本概念基本概念 控制器包括有限个状态，状态与状态之间存在着控制器包括有限个状态，状态与状态之间存在着某种转换关系。每当在某一状态下读入一个字符某种转换关系。每当在某一状态下读入一个字符时，便使状态发生改变（称为状态转换）。时，便使状态发生改变（称为状态转换）。状态转换包括以下几种情况：状态转换包括以下几种情况：1)1)转换到其自身，转换到其自身，即保持当前状态不变；即保持当前状态不变；2)2)转换的后继状态只有一转换的后继状态只有一个；个；3)3)转换的后继状态有若干个。转换的后继状态有若干个。如果一个有限自动机每次转换的后继状态都是唯如果一个有限自动机每次转换的后继状态都是唯一的
8、，称为确定的有限自动机（一的，称为确定的有限自动机（DFADFA）；如果转换）；如果转换的后继状态不是唯一的，则称为不确定的有限自的后继状态不是唯一的，则称为不确定的有限自动机（动机（NFANFA）。）。通常把有限自动机开始工作的状态称为通常把有限自动机开始工作的状态称为“初始状初始状态态”，把结束工作的状态称为，把结束工作的状态称为“终止状态终止状态”或或“接受状态接受状态”。6.1 6.1 基本概念基本概念 确定的有限自动机的形式化定义确定的有限自动机的形式化定义确定的有限自动机是一个五元组确定的有限自动机是一个五元组其中：其中：有限的状态集合；：有限的状态集合；：有限的输入字母表；：有限
9、的输入字母表；：转换函数，是转换函数，是 到到 的的映射；映射；：初始状态，初始状态，；：终止状态集，终止状态集，；QT0qFTQQQF 6.1 6.1 基本概念基本概念Qq 0),(0FqTQM（初始状态只有一个）（初始状态只有一个）为了描述一个有限自动机的工作状况，可采用为了描述一个有限自动机的工作状况，可采用。状态转换图是一个有向图，图中。状态转换图是一个有向图，图中的每个节点表示一种状态，一条边（或弧）表的每个节点表示一种状态，一条边（或弧）表示一个转换关系。示一个转换关系。q0q1q3q2aabbb初始状态：初始状态：q0q0终止状态：终止状态：q3q3控制器的状态集合：控制器的状态
10、集合：q0,q1,q2,q3q0,q1,q2,q36.1 6.1 基本概念基本概念a a有限自动机的状态转换图有限自动机的状态转换图q0q1q3q2aabbab状态集合状态集合字母表字母表初始状态初始状态终止状态集终止状态集转换函数转换函数,3210qqqqQ,baT 3qF 0q10),(qaq20),(qbq31),(qaq11),(qbq22),(qaq32),(qbq),(3aq),(3bq 用于识别输入的字符串是否是 或者 形式的有限自动机。aabnbbanl 存储程序的计算机本身也可以认为是一个有限存储程序的计算机本身也可以认为是一个有限状态机。输入输出都是离散量，某时刻的状态状态
11、机。输入输出都是离散量，某时刻的状态由当时进行的操作、寄存器、主存储器和辅助由当时进行的操作、寄存器、主存储器和辅助存储器中存储内容确定。存储器中存储内容确定。l 一个运行中的程序在不同时刻也具有不同的状一个运行中的程序在不同时刻也具有不同的状态，程序执行中的状态就是各种态，程序执行中的状态就是各种“变量变量”当时当时所存放的值。比如我们设计的求所存放的值。比如我们设计的求5 5！的程序，！的程序，初始进入循环前的状态是：初始进入循环前的状态是：(p=1 and i=2),(p=1 and i=2),执行完循环后的状态是：（执行完循环后的状态是：（p=40 and i=6p=40 and i=
12、6）。）。6.1 6.1 基本概念基本概念6.2 6.2 程序设计实例研究程序设计实例研究应用有限自动机模型求解问题的核心问题就是抽象出状应用有限自动机模型求解问题的核心问题就是抽象出状态，描述出状态转移图和状态转移函数态，描述出状态转移图和状态转移函数应用有限自动机解题步骤应用有限自动机解题步骤1 1、确定输入集、确定输入集2 2、绘制状态迁移图（确定状态，在每一个状态下对输入、绘制状态迁移图（确定状态，在每一个状态下对输入进行分类，确定下一个状态）进行分类，确定下一个状态）3 3、确定状态转移函数（在某状态下，接收到某一字符后、确定状态转移函数（在某状态下，接收到某一字符后，自动机要执行的
13、操作，以及迁移到的下一状态），自动机要执行的操作，以及迁移到的下一状态）设计交通车辆观测统计算法。设计交通车辆观测统计算法。问题描述：在一个路口设置一个探测器，通过通信线路连问题描述：在一个路口设置一个探测器，通过通信线路连接到后台的计算机。路口每通过一辆汽车，探测器向接到后台的计算机。路口每通过一辆汽车，探测器向计算机发出一个车辆信号计算机发出一个车辆信号11，探测器每隔，探测器每隔1 1秒钟向秒钟向计算机发出一个时钟信号计算机发出一个时钟信号00，观测结束向计算机发，观测结束向计算机发出结束信号出结束信号。要求在计算机上设计一个程序，能够接收探测器发出的信要求在计算机上设计一个程序，能够接
14、收探测器发出的信号，统计出观测的时长、在观测时长内通过的车辆总号，统计出观测的时长、在观测时长内通过的车辆总数、以及两辆车之间最大的时间间隔。数、以及两辆车之间最大的时间间隔。问题分析：探测器向计算机发出的信号可以认为是一个问题分析：探测器向计算机发出的信号可以认为是一个任意长的字符序列（以任意长的字符序列（以EOFEOF结束），比如：结束），比如：“011011000111101”011011000111101”，这样设计程序实际上演变为读取，这样设计程序实际上演变为读取该字符序列，然后进行相关的操作。该字符序列，然后进行相关的操作。11观测时长观测时长：字符序列中：字符序列中0 0的个数的
15、个数(6(6秒秒)；车辆总数车辆总数：字符序列中：字符序列中1 1的个数的个数(9(9辆辆)；两车间最大时间间隔两车间最大时间间隔：两个：两个1 1之间的最大连续之间的最大连续0 0的个数的个数(3(3秒秒)；6.2 6.2 程序设计实例研究程序设计实例研究 重新审题：我们所设计的程序就是读入以重新审题：我们所设计的程序就是读入以EOFEOF结束的由结束的由00或者或者11组成的字符串，这个组成的字符串，这个字符串可以映射为有限自动机模型中的字符输字符串可以映射为有限自动机模型中的字符输入带，我们的任务就是设计控制器程序逐字符入带，我们的任务就是设计控制器程序逐字符地读取输入带，进行处理并引起
16、控制器的状态地读取输入带，进行处理并引起控制器的状态改变，最终产生输出，因此这个问题的求解就改变，最终产生输出，因此这个问题的求解就抽象为一个有限自动机。抽象为一个有限自动机。6.2 6.2 程序设计实例研究程序设计实例研究交通灯观测实例研究交通灯观测实例研究-解法解法1 11 1、确定输入集、确定输入集T T11，00，EOFEOF 2 2、每接收一类输入都认为进入、每接收一类输入都认为进入一个固定状态，加上初始状态一个固定状态，加上初始状态，共，共4 4个状态个状态 q0q0：初始状态：初始状态 q1 q1：接收到：接收到1 1后的状态后的状态 q2 q2：接收到：接收到0 0后的状态后的
17、状态 q3 q3：接收到：接收到EOFEOF后的终止状后的终止状态态3 3、绘制状态迁移图，确定状态、绘制状态迁移图，确定状态转换函数（每一个状态下对输转换函数（每一个状态下对输入集进行分类，确定转换函数入集进行分类，确定转换函数）3 3、确定转换函数、确定转换函数 当前状态是当前状态是q0(state=q0)q0(state=q0)：读入读入11：vehicles+;state=q1vehicles+;state=q1读入读入00：seconds+;state=q2seconds+;state=q2读入读入EOFEOF：state=q3state=q3 当前状态是当前状态是q1(state=
18、q1)q1(state=q1)：读入读入11：vehicles+;vehicles+;读入读入00：interval=1;seconds+;state=q2interval=1;seconds+;state=q2读入读入EOFEOF：state=q3state=q3),(0FqTQM 当前状态是当前状态是q2(state=q2)q2(state=q2)：读入读入11：if(vehicles0)if(vehicles0)处理最大处理最大时长时长 vehicles+;vehicles+;state=q1state=q1读入读入00：seconds+;seconds+;if(vehicles0)if
19、(vehicles0)interval+;interval+;读入读入EOFEOF：state=q3state=q3终止状态集终止状态集F=q3F=q3),(0FqTQM有限自动机解题通用处理模式有限自动机解题通用处理模式解法解法2 2对应代码对应代码：解法解法1 1对应代码：对应代码：此处自动机此处自动机会有不同处会有不同处理理交通灯观测实例研究交通灯观测实例研究-解法解法2 21 1、确定输入集、确定输入集T T11，00，#2 2、对解法、对解法1 1的输入集状态，按照接收输入后可能出现的不同的输入集状态，按照接收输入后可能出现的不同“动作动作”进行细分，确定细分状态进行细分，确定细分状
20、态:输入输入00后的状态细分后的状态细分n此前从未出现此前从未出现11：若接收到这样的：若接收到这样的0,0,则系则系统进入状态统进入状态 q1q1n此前出现过此前出现过11 ：若接收到这样的：若接收到这样的0,0,则系统则系统进入状态进入状态 q2q2输入输入11后的状态细分后的状态细分n这是第一个这是第一个11：进入状态：进入状态 q3q3n这不是第一个这不是第一个11，且前面是，且前面是00：进入状态：进入状态 q4q4n这不是第一个这不是第一个11，且前面是，且前面是1:1:进入状态进入状态 q5q5#n进入结束状态进入结束状态 q6q6交通灯观测实例研究交通灯观测实例研究-解法解法2
21、 23、绘制状态迁移图绘制状态迁移图说明：在说明：在q0q5q0q5的任何一个状态的任何一个状态下，如果接收到下，如果接收到字符字符#,#,则进则进入终止状态入终止状态q6q6。此处为了保持图此处为了保持图的简洁，没有画的简洁，没有画出到出到q6q6的迁移。的迁移。交通灯观测实例研究交通灯观测实例研究-解法解法2 24 4、确定状态转移函数、确定状态转移函数当前状态是当前状态是q0q0n读入读入11：vehicles+;state=q3vehicles+;state=q3n读入读入00：seconds+;state=q1seconds+;state=q1n读入读入#：state=q6state
22、=q6当前状态是当前状态是q1q1n读入读入11：vehicles+;state=q3vehicles+;state=q3n读入读入00：seconds+;seconds+;n读入读入#：state=q6state=q6交通灯观测实例研究交通灯观测实例研究-解法解法2 24 4、确定状态转移函数（续）、确定状态转移函数（续）当前状态是当前状态是q3q3n读入读入11：vehicles+;state=q5vehicles+;state=q5n读入读入00：seconds+;seconds+;interval+;state=q2interval+;state=q2n读入读入#：state=q6st
23、ate=q6当前状态是当前状态是q5q5n读入读入11：vehicles+;vehicles+;n读入读入00：seconds+;seconds+;interval+;state=q2interval+;state=q2n读入读入#：state=q6state=q6交通灯观测实例研究交通灯观测实例研究-解法解法2 24 4、确定状态转移函数（续）、确定状态转移函数（续）当前状态是当前状态是q2q2n读入读入11：vehicles+vehicles+；if(intervallongest)if(intervallongest)longest=interval;longest=interval;i
24、nterval=0;interval=0;state=q4 state=q4n读入读入00：seconds+;seconds+;intervalinterval+;+;n读入读入#：state=q6state=q6当前状态是当前状态是q4q4n读入读入11：vehicles+;state=q5vehicles+;state=q5n读入读入00：seconds+;seconds+;intervalinterval+;+;state=q2state=q2n读入读入#：state=q6state=q66.2 6.2 程序设计实例研究程序设计实例研究例例2 2 检验输入是否是合法的检验输入是否是合法的
25、C C语言注释语言注释/*/q1:q1:等待等待*状态状态q2q2：注释开始状态：注释开始状态q3:q3:等待等待/以结束注以结束注释状态释状态q4q4：已接收注释结：已接收注释结束状态束状态6.2 6.2 程序设计实例研究程序设计实例研究 转换函数分析转换函数分析startstart状态下：状态下：n输入输入/:state=q1/:state=q1n输出非输出非/:state=ERROR/:state=ERRORq1q1状态下：状态下：n输入输入*:state=q2:state=q2n输出非输出非*:state=ERROR:state=ERRORq2q2状态下：状态下：n输入输入*:stat
26、e=q3:state=q3n输入输入EOFEOF：state=ERRORstate=ERRORn输出其他输出其他:state=q2:state=q26.2 6.2 程序设计实例研究程序设计实例研究 转换函数分析转换函数分析(续）续）q3q3状态下：状态下：n输入输入*:状态不变状态不变n输入输入/:state=q4/:state=q4n输入输入EOFEOF：state=ERRORstate=ERRORn输出其他输出其他:state=q2:state=q2q4q4状态下：状态下：n输入输入EOFEOF：state=ACCEPTstate=ACCEPTn输出其他输出其他:state=ERROR:state=ERROR6.2 6.2 程序设计实例研究程序设计实例研究 例例3 3 去除去除C C语言注释语言注释
