第三章有穷自动机.ppt
《第三章有穷自动机.ppt》由会员分享,可在线阅读,更多相关《第三章有穷自动机.ppt(50页珍藏版)》请在三一文库上搜索。
1、第三章 有穷自动机,本章介绍有关有穷自动机的基本概念和理论以及正规文法、正规表达式与有穷自动机之间的相互关系。,3.1 概述有穷自动机的意义,有穷状态自动机(Finite-state Automata FSA)或简称FA是具有离散的输入输出系统的数学模型。系统内部具有有穷个状态,系统的状态概括了对过去输入状况的处理信息,系统只需根据当前所处的状态和面临的输入就可以决定系统的后继行为,系统处理了当前的输入后,系统的内部状态也将发生变化。电梯控制装置、文本编辑程序、编译技术中的词法分析程序,计算机以及人脑都是有穷状态系统。,1-9 1,3,5,7,9,3.1 概述有穷自动机的模型,1 0 4 3
2、9 7,T,A,S,1,3,5,7,9,输入带,有穷控制器,读头,0-9,3.2 有穷自动机的形式定义,定义3.1 一个确定有穷自动机DFSA是一个五元组 M=(Q, , t, q0, F) 其中, Q:是非空有穷状态集,其中的每个元素称为一个状态; :是有穷输入字母表,它的每一个元素称为一个输入 符号; t :是一个单值映射QQ,也称状态转换函数,t(q,x)=q意指:当现行状态为q,面临的输入符号为x时,将转到下一状态q,q称为q的一个后继状态; q0Q称之为开始状态; FQ称为终止状态集,至少由一个终止状态组成。,3.2.1 状态转换表(矩阵),DFA转换矩阵: 该矩阵行表示状态集; 列
3、表示输入字母表; 矩阵元素表示 t(q,a)的值。即某行状态面临某列输入字符所唯一转向的下一个状态。 该矩阵称为状态转换矩阵,3.2.1 状态转换表(矩阵),例3.1 有穷自动机 A=(Q, , t, q0,F) 其中,Q= S,A,B,G,H,=+,-,d,S是开始状态,终止状态集F=B,H,映射t:QQ由下表所示的状态转换表给出。,3.2.2 状态转换图(1),一个DFA也可表示成一张状态转换图。 DFA状态:用圆圈节点表示; 初始状态节点:用“右向双(单)箭头”表示; 终止状态节点:用“双圈”表示; 状态变迁:用单向弧线表示,上面必须标记激励变迁的符号。,3.2.2 状态转换图,例3.2
4、 有穷自动机A(记为DFSA A), A=(Q, , t, q0,F) 其中,Q= q0, q1, q2, q3,=a, b,q0是开始状态,终止状态集F=q0,映射t:QQ由下图所示的状态转换图给出。 在图中,状态q0用双 圆圈标记,表明它是终止 状态;同时,用一个箭头 标记,表明它是开始状态。,3.2.3 构形和移动(1),对于一个给定的输入串,假定一个DFSA 已经完成了若干次移动,为了预测它的进一步行为,只需要知道”当前状态”和”尚待扫描的输入串”,这两类信息对于在某一次的特定应用中,位于某个特定时刻的DFSA提供了一种完整的描述,这种描述就称为构形。,3.2.3 构形和移动(2),构
5、形(q0,)称为初始构形,其中q0是初始状态,是由该自动机可接收或拒绝的任何输入串。构形(q, )称为终止构形,其中是空串,qF(终态集)。 自动机的移动(记为)是从一种构形到另一种构形的转换。 DFSA的工作过程就是一系列的移动过程。 记号+称为的传递闭包;*称为的自反闭包。 *表示“0次或多次移动”;+表示“一次或多次移动”。,3.2.3 构形和移动(3),DFSA M 所识别的语言L(M)可表示为: L(M)=*(q0,)*(q,)q F,自动机接受(识别)字符串,1)自动机所接收字符 如果对某一自动机M=( Q, , t, q0, F) x , 有t( q0,x)=P,且P F ,则称
6、字符x被自动机所接收。 2)自动机所接收输入串 自动机从开始状态读完全部输入串后,自动机恰好到达终止状态,则称输入串被自动机所接收。,自动机接受(收)字符串,3)自动机接收语言 自动机M所能接收的串组成一个集合,则称该集合为自动机M所能接收(识别)的语言。 用L(M)表示: L(M) t(q0, ) F , * ,3.2.4 自动机的等价性,定义3.2 M和M是等价的,当且仅当对每一个串x,M接收x当且仅当M接收x。 定义3.3 如果M仅通过重新标记它的状态就能转换称M,则M和M称为同构的(Isomorphic)。 FSA的一个基本定理是:对每一个自动机M,存在一个等价的具有最少状态个数的自动
7、机M,而且对于每一个其状态个数与M相同且等价于M的自动机M,必是与M同构的。换句话说,M在结构上是唯一的。,3.2.5 非确定有穷状态自动机,定义3.4 一个非确定有穷自动机NDFSA是一个五元组 NDFSA=(Q, , t, q0, F) 其中,Q是一个非空有穷状态集, 是一个非空有穷输入字母集, 映射t为QQ的子集(即t是一个多值映射), Q0Q是开始状态集, FQ是终止状态集。 同样的,NDFSA也可以用状态转换表和状态转换图表示。,3.2.5 非有穷状态自动机,非确定有穷自动机与确定有穷自动机的主要区别有三: 1NDFSA有一个开始状态集,而DFSA只有一个开始状态。 2NDFSA的映
8、射是QQ的子集,是一个多值映射,而DFSA的映射是QQ,是一个单值映射。 3NDFSA在没有扫描任何输入符号的情况下,也可以进行移动,这种移动称为空移。我们用表示法: t(q, )=某些状态的集合将这种情况包括在状态转换函数中。注意,甚至当输入串已经完全扫描完之后还可能需要空移。,3.3 NDFSA到DFSA的转换,3.3.1 NFA 的确定化 NFA确定化的定义 NFA的确定化是指对任意给定的NFA都能相应地构造一DFA,使它们接受相同的语言。,NDFSA到DFSA的转换,NFA确定化为DFA的方法子集法 对于一个NFA ,由于状态转换函数t是一个多值函数,因此总存在一些状态q,对于它们有t
9、(q,a)=q1,q2,q3,qn, 它们是NFA状态集合的一个子集,为了NFA转化为DFA,把状态集合 q1,q2,q3,qn看作一个状态A,也就是说让DFA 的每一个状态代表NFA状态集合的某个子集,这个DFA使用它的状态去记录在NFA读入输入符号之后可能到达的所有状态的集合,这样就可以把NFA转化为DFA了。这种构造方法称为子集法。,NDFSA到DFSA的转换,利用构造-closure的方法将NFA确定化为DFA 定义3.5:设NDFSA M=(Q, , t, Q0, F),假定I是M中状态集的一个子集,定义-closure(I)如下: 若qI,则qclosure(I); 若q-clos
10、ure(I),q是由q出发经多条弧所到达的状态,则q -closure(I)。 定义3.6假定I是NDFSA M中状态集的一个子集,a,定义 Ia=-closure(J) 其中J是所有那些可从子集I中的任一状态出发,经过一条a连线(跳过a连线前的连线)而到达的状态(结)的全体。,NDFSA到DFSA的转换,NFA N=(Q, ,T,S,Z) DFA M =(Q, , T,S,Z) (1)首先将从 NFA N的初态S出发经过任意条弧所能到达的状态组成的集合作为确定化后的 DFA M 的初态S。 (2)从S出发,经过对任意输入符号a的状态转移所能到达的状态(包括读入输入符号a之后所有可能的转移所能
11、到达的状态)所组成的集合作为M的新状态。,NDFSA到DFSA的转换,(3)如此重复,直到不在有新的状态出现为止。 (4)在所产生的状态中,含有原NFA终态的子集作DFA的终态。,消除不可达状态,在自动机中,从开始状态没有任何一条路径能达到的状态称为不可达状态。由于不可达状态事实上是无用的,因此也称多余的状态,可以删除它们。下面给出识别可达状态的算法。当该算法终止时,每一个未标记的状态就是不可达状态。 识别DFSA中可达状态的算法。 标记开始状态S; 给定任意标记过的状态P,如果对某个输入符号存在从状态P到Q的转换,则标记每一个这样的状态Q; 重复步骤,直到不再有可标记的状态为止。,3.3.2
12、 DFA的化简 (最小化),DFA的化简 所谓DFA的化简是指寻找一个状态数比M少的确定的有穷自动机M,使得L(M)= L(M)。 化简后的DFA M应满足两个条件: (1)没有多余状态;(不可达状态) (2)它的状态集合中,没有两个状态是相互等价的。 定义3.7 假定q1和q2是M中的两个不同状态,称q1和q2是等价的当且仅当如果从状态q1出发能扫描任意串w而停止于终态,那么从状态q2出发也能扫描同一个串w而停止于终态; 定义3.8 如果两个状态q1和q2不等价,则称这两个状态是可区分的。,3.3.2 DFA的化简 (最小化),化简方法 DFA M 最小化的方法是把M的状态集合Q划分成一些不
13、相交的子集,使得每个子集中的任何两个状态是等价的,而任何两个属于不同子集的状态都是可区分的;然后在每个子集中任取一个状态作为代表,而删去子集中其余状态,并把射向其余状态的弧都改为射向作为“代表”的状态中。,3.3.2 DFA的化简 (最小化),化简的具体步骤: (1)将DFA M的状态集Q分成两个子集:终态集F和非终态集Q-F,形成初始分划。 (2)对建立新的分划New ,对的每个状态子集G,进行如下变换: 把G分划成新的子集,使得G的两个状态s 和t属于同一子集,当且仅当对任何输入符号a,状态s和t转换到的状态都属于的同一子集。 用G分划出的所有新子集替换G,形成新的分划New 。,3.3.
14、2 DFA的化简 (最小化),( 3)如果New,则执行第(4)步;否则令= New ,重复第(2)步。 (4)分划结束后,对分划中的每个状态子集,选出一个状态作代表,而删去其他一切等价的状态,并把射向其他状态的箭弧改为射向这个作为代表的状态。这样得到的DFA M是与DFA M等价的一切DFA中状态数最少的DFA。 举例.,3.3.3从化简后的DFA到程序表示,识别标识符的DFSA1(见图 (a))需改为图 (b)所示状态,其中,l代表字母,d代表数字。 图 (a) 图(b) 如果赋予状态q0、q1与q2一定的操作,则可得识别单词标识符的程序流程图(见下图)。,3.4 正规文法与有穷自动机,正
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第三 有穷 自动机
链接地址:https://www.31doc.com/p-3139764.html