《有穷自动机》PPT课件

*,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,Click to edit Master title style,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,Click to edit Master title style,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Compiler,编 译 原 理,Wednesday, March 13, 2013,（1）分析和识别单词及属性，,包括识别语言的关键字、标识符、常数、运算符等；,（2）跳过各种分隔符，如空格，回车，制表符等；,（3）删除注释；,（4）进行词法检查，报告所发现的错误；,（5）建立符号表。,词法分析的任务,Compiler,编 译 原 理,Wednesday, March 13, 2013,有穷自动机,标识符,无符号整数,单界符,双界符,S,1,非字母数字,字母,字母、数字,2,非数字,数字,数字,3,其他字符,+ * ，,（ ）,出口,4,其他字符,5,=,非 =,出错,其他,读字符,查保留字表,返回S,状态图的形式化描述,Compiler,编 译 原 理,Wednesday, March 13, 2013,有穷自动机是一种,数学模型,，具有离散的输入与输出，系统可处于有穷状态中的任何一个,它能准确地,识别正规集,，即识别正规文法所定义的语言和正规式所表示的集合,引入有穷自动机这个理论，正是为,词法分析程序的自动构造,寻找特殊的方法和工具,有穷自动机分为两类：,确定的有穷自动机,（DFA）,(Deterministic Finite Automata),不确定的有穷自动机,（NFA）,(Nondeterministic Finite Automata),Compiler,编 译 原 理,Wednesday, March 13, 2013,2型文法,（不确定的下推自动机）,1型文法,（不确定的界限自动机）,0型文法,（图灵机）,3型文法,（有限自动机）,Compiler,编 译 原 理,Wednesday, March 13, 2013,1.确定的有穷自动机（DFA）,M=(, Q, f,S, Z),：有穷字母表，它的每个元素称为一个输入符号,Q：有穷集，它的每个元素称为一个状态,SK，是唯一的初态,Z,K是一个终态集，终态也称可接受状态或结束状态,f是转换函数，是QQ上的单值映射：,f（q1，a）=q2,Compiler,编 译 原 理,Wednesday, March 13, 2013,状态转移函数f可用一矩阵来表示：,输入,字符,状态,a b,0 1 2,1 3 2,2 1 3,3 3 3,例如: M:（0,1,2,3,a,b,f，0，3）,f（0，a）=1 f（0，b）=2,f（1，a）=3 f（1，b）=2,f（2，a）=1 f（2，b）=3,f（3，a）=3 f（3，b）=3,所谓确定的状,态机，其确定,性表现在状态,转移函数是单,值函数！,字母表,含有n个,输入字符，那末,任何一个状态结,点最多有n条弧,射出，而且每条,弧以一个不同的,输入字符标记。,M=(, Q, f,S, Z,),Compiler,编 译 原 理,Wednesday, March 13, 2013,一个DFA也可以用一状态转换图表示：,输入,字符,状态,a b,0 1 2,1 3 2,2 1 3,3 3 3,DFA的状态图表示：,1,0,3,2,a,a,b,b,a,b,b,a,字母表,含有n个,输入字符，那末,任何一个状态结,点最多有n条弧,射出，而且每条,弧以一个不同的,输入字符标记。,Compiler,编 译 原 理,Wednesday, March 13, 2013,换言之：若存在一条初始状态到某一终止状态的路径，且这条路径上所有弧的标记符号连接成符号串，则称为DFA M（接受）识别。,DFA M所接受的语言为：L(M)=|,f(S,)=S,n,S,n,Z,DFA M所能接受的符号串的全体记为L(M),若M的初态结点同时为终态，或者存在一条从初态到某个终态结点的通路，则为M所识别。,Compiler,编 译 原 理,Wednesday, March 13, 2013,（0，abaab）,=（1，baab）,=（2，aab）,=（1，ab）,=（3，b）,=3 (接受),DFA的状态图表示：,1,0,3,2,a,a,b,b,a,b,b,a,（0，abab）,=（1，bab）,=（2，ab）,=（1，b）,=2 (拒绝),对于符号串abaab,对于符号串abab,Compiler,编 译 原 理,Wednesday, March 13, 2013,f是一个多值函数，是从Q*到Q的子集的映射：,f：Q,2,Q,其中,2,Q,是Q的幂集，即Q中所有子集组成的集合。,2.不确定的有穷自动机（NFA）,M=(, Q, f,S, Z),有穷自动机的不确定性表现在在某个状态下，对于某个输入字符存在多个后继状态，即状态的转向是不确定的,Compiler,编 译 原 理,Wednesday, March 13, 2013,例： NFA N=(a,b,c ,1,2,3,4, f,1,4),符号,状态, a b c,1 4 2，3 ,2 2 4 ,3 3，4,4 ,Compiler,编 译 原 理,Wednesday, March 13, 2013,对于*上的任何符号串,，若存在一条从某一初态到某一终态的通路，且该通路上所有弧的标记字符依次连接成的串等于,，则称,可以被NFA N所识别或接受。,若N的初态结点同时为终态，或者存在一条从初态到某个终态结点的,通路，则,为N所识别。,NFA N所能识别的符号串的全体记为L(N)，称为NFA N所识别的语言,Compiler,编 译 原 理,Wednesday, March 13, 2013,上例题相应的状态图为：,1,2,3,4,a,b,a,c,a,c,N所接受的语言（正规式） R=aa,*,b|ac*c|,符号,状态, a b c,1 4 2，3 ,2 2 4 ,3 3，4,4 ,Compiler,编 译 原 理,Wednesday, March 13, 2013,能接受,000,111,1010001,110000001,(0|1),*,(000|111)(0|1),*,不能接受,00,01100,Compiler,编 译 原 理,Wednesday, March 13, 2013,画出能够识别C语言注释/* */的DFA,1,2,4,5,3,others,others,/,*,*,*,/,6,others,others,all,all,Compiler,编 译 原 理,Wednesday, March 13, 2013,1,2,4,5,3,others,others,/,*,*,*,/,状态1：注释开始状态。,状态2：进入注释体前的中间状态。,状态3：表明目前正在注释体中的状态。,状态4：离开注释前的中间状态。,状态5：注释结束状态，即接受状态。,Compiler,编 译 原 理,Wednesday, March 13, 2013,用于某些重要软件的设计和构造,设计和检查数字电路行为的软件;,扫描如网页族等大规模文本以发现字、词或其它结构的出现频率的软件;,验证所有只有有限多个不同状态的系统的软件，这类系统包括通信协议和信息安全交换协议。,有穷自动机的其它应用,阅读两篇论文,基于协议分析状态机的入侵检测系统,有限自动机在BBS信息监测系统中的运用,Compiler,编 译 原 理,Wednesday, March 13, 2013,已证明：非确定的有穷自动机与确定的有穷自动机从功能上来说是等价的，也就是说，我们能够从：,NFA N,DFA M,构造成一个,使得 L(M)=L(N),DFA是NFA的特例。有一种算法，将NFA转换成接受同样语言的DFA.,Compiler,编 译 原 理,Wednesday, March 13, 2013,已证明：非确定的有穷自动机与确定的有穷自动机从功能上来说是等价的，也就是说，我们能够从：,NFA M,DFA M,构造成一个,使得 L(M)=L(M),DFA是NFA的特例。有一种算法，将NFA转换成接受同样语言的DFA.这种算法称为,子集法,.,与某一NFA等价的DFA不唯一,3. NFA的确定化,Compiler,编 译 原 理,Wednesday, March 13, 2013,从NFA的矩阵表示中可以看出，表项通常是一状态的集合，而在DFA的矩阵表示中，表项是一个状态。,NFA到相应的DFA的构造的基本思路是：,DFA的每一个状态对应NFA的一组状态.,符号,状态, a b c,1 4 2，3 ,2 2 4 ,3 3，4,4 ,1,2,3,4,a,b,a,c,a,c,Compiler,编 译 原 理,Wednesday, March 13, 2013,(1) 合并,如果有 ，则把S,2,合并到S,1,S,1,S,2,转换需解决的问题：,i,j,k,m,a,b,a,n,（a）,i,j,m,k,a,a,b,n,（b）,Compiler,编 译 原 理,Wednesday, March 13, 2013,(2)状态合并,0,1,2,3,a,a,b,c,（a）,0,1,2,3,a,b,c,（b）,Compiler,编 译 原 理,Wednesday, March 13, 2013,定义1,状态集合I的,-闭包，表示为,-closure(I), 若qI，则q,-closure(I)；, 若qI，则从q出发经过任意条,弧而能到达的任何状态q都属于,-closure(I)。,为了使得NFA确定化，我们首先给出两个定义,：,_,closure(I),I,I,S,2,S,2,S,1,S,1,S,3,S,3,Compiler,编 译 原 理,Wednesday, March 13, 2013,例：,如图所示的状态图：,令I=1，,求-closure（I）=？,1,5,6,4,3,2,a,a,a,根据定义：,-closure（I）=1，3,课堂练习：,令I=1,2，,求-closure（I）=？,Compiler,编 译 原 理,Wednesday, March 13, 2013,I是状态集，由I中的状态出发，经过一条a弧可能到达的状态的集合称为move（I，a），则,I,a,= _closure ( move( I , a ) ),定义2,I,a,子集,Compiler,编 译 原 理,Wednesday, March 13, 2013,例：令 I=1,Ia=-closure(move（I，a）),=-closure(f（1，a）,=-closure(2，4）=2，4，6,根据定义1，2，可以将上述的M确定化（即可构造出状态,转换矩阵）,1,5,6,4,3,2,a,a,a,课堂练习：,令I=1,2,3,求,Ia,=？,Compiler,编 译 原 理,Wednesday, March 13, 2013,课堂练习：,令I=1，设,S,= -closure（I），求,S,？,S,a,=？,将从状态S出发经过任意条,弧所能到达的状态作为DFA的初态S,从S出发，把遇到输入符号a所转移到的后继状态集作为DFA的新状态,如此重复，直到不再有新的状态出现为止,NFA转换为DFA的思想,1,2,3,4,a,b,a,c,a,c,Compiler,编 译 原 理,Wednesday, March 13, 2013,I I,a,I,b,I,c,1,4 2,3 ,2,3 2 4 3,4,2 2 4 ,4 ,3,4 3,4,（1）构造一张表，它共有+1列,（2）第一行第一列为,-closure(S),（3）求Ia,（4）重复步骤（3）,（5）将状态子集重新命名,1,2,3,4,a,b,a,c,a,c,Compiler,编 译 原 理,Wednesday, March 13, 2013,将求得的状态转换矩阵重新编号,DFA M状态转换矩阵：,符号,状态,a,b,c,0,2,3,4,1,2,2,1,_,_,_,_,_,_,_,_,3,3,4,4,Compiler,编 译 原 理,Wednesday, March 13, 2013,DFA M的状态图：,注意：包含原初始状态1的状态子集为DFA M的初态,包含原终止状态4的状态子集为DFA M的终态。,0,1,4,2,3,1,4,2,3,4,2,a,c,a,b,b,c,3,4,1,2,3,4,a,b,a,c,a,c,Compiler,编 译 原 理,Wednesday, March 13, 2013,课堂练习,4,f,3,5,6,2,1,i,a,a,a,a,b,b,b,b,start,Compiler,编 译 原 理,Wednesday, March 13, 2013,等价的DFA,a,C,D,B,A,E,F,S,b,a,a,a,a,a,b,b,b,b,b,a,b,F,start,Compiler,编 译 原 理,Wednesday, March 13, 2013,4. DFA的最小化,如果不同的DFA能识别相同的语言，则称它们是等价的DFA。,在等价的DFA中，如果某一个DFA的状态数是最少的，则这个DFA是最简的。,对于任一个,DFA，存在一个唯一的状态最少的等价的DFA,最简的DFA,它没有多余状态和等价状态,Compiler,编 译 原 理,Wednesday, March 13, 2013,定义1,多余状态：,从开始状态出发,任何输入串也不能到达的状态,0,1,s,0,s,1,s,2,s,3,s,5,s,7,s,1,s,5,s,1,s,2,s,2,s,5,s,5,s,1,s,1,s,3,s,0,s,1,0,1,s,0,s,1,s,2,s,3,s,4,s,5,s,6,s,7,s,8,s,1,s,5,s,7,s,2,s,2,s,5,s,5,s,7,s,5,s,6,s,1,s,3,s,8,s,0,s,0,s,1,s,3,s,6,例:,画状态图可以看出s,4,s,6,s,8,为不可达状态应该消除,Compiler,编 译 原 理,Wednesday, March 13, 2013,定义2,等价状态 状态s和t的等价条件是:, 状态S和T必须同时为终态或非终态, 对于所有输入符号，S和T必须转换到等价的状态里,Compiler,编 译 原 理,Wednesday, March 13, 2013,把DFA的状态划分成一些不相交的子集,任何不同的两个子集的状态都是可区分的,同一子集中的任何两个状态都是等价的,5,7,2,4,3,6,1,srart,a,a,a,a,a,a,a,b,b,b,b,b,b,b,DFA最小化算法的基本思想(没有多余状态)：,Compiler,编 译 原 理,Wednesday, March 13, 2013,解:,(一)区分终态与非终态,1,2,3,4,5,6,6,3,7,3,1,5,4,6,7,3,7,4,1,4,2,1,2,a,b,区号,1,2,3,1,2,3,4,5,6,6,3,7,3,1,5,4,6,7,3,7,4,1,4,2,a,b,区号,（1）将所有状态分成两个子集：终态集和非终态集,（2）把等价的状态构成一个子集，若不等价继续划分,（3）结束后，重新标号或从每个子集中选一个状态做代表,Compiler,编 译 原 理,Wednesday, March 13, 2013,1,2,3,4,5,6,6,3,7,3,1,5,4,6,7,3,7,4,1,4,2,a,b,1,2,4,3,1,2,4,3,1,2,3,4,5,6,6,3,7,3,1,5,4,6,7,3,7,4,1,4,2,a,b,5,区号,区号,Compiler,编 译 原 理,Wednesday, March 13, 2013,将区号代替状态号得:,1,2,3,4,5,a,b,5,2,1,4,3,5,5,2,3,1,1,5,5,2,4,3,a,a,a,a,a,b,b,b,b,b,化简后的有穷自动机具有较少的状态，实现起来更加简洁。,正规表达式的引入：,对自动生成词法分析程序而言，正规表达,式也是非常有用的工具。,所谓,正规表达式,就是用特定的,运算符,及,运算对象,按某种规则构造的表达式。例如：c-语言的词法。,正规表达式用来描述单词,结构,(定义单词)。,正规表达式(也称正则表达式),就是用特定的,运算符,及,运算对象,按某种规则构造的表达式。,每个正规表达式代表一个,字符串的集合,，我们把其称为正规集。,语言,(Language)是字符串组成的集合，我们也可以把正规表达式表示的,正规集,称为该正规表达式表示的,语言,。,正规表达式和它所表示的正规集(字符串的集合)的递归定义如下：,设有字母表为，辅助字母表=,|,.,*,(,),(1)和是上的正规式，它们所表示的正规集分别为和;,(2) 若a，则a是上的正规式，它所表示的正规集为a;,若r和s都是上的,正规式,，且它们所表示的,正规集,分别为L(r)和L(s)，那么：,r|s,是,正规式,，表示的,正规集,为,L(r|s)=L(r)L(s) ；,rs,是,正规式,，表示的,正规集,为,L(rs)=L(r)L(s) ；,r,*,是,正规式,，表示的,正规集,为(L(r),*,。,(r) 是,正规式,，表示的,正规集,为L(r)；,(4)仅由有限次使用上述三步骤而定义的表达式才是上的,正规式,，,仅由这些正规式所表示的符号串集合才是上的,正规集。,注：算符的优先级为先“ * ”，再“ . ”最后“ | ” ,都是左结合的，它们满足结合律。,举例： C-,语言的词法,例1，令,=a，b，,上的正规式和相应的正规集的例子：,正规式 正规集,a,a,a,b,ab,(a,b)(a,b),a,a,b,ab,aa,ab,ba,bb,a,aa, 任意个a的串,(a,b),a,b,*,即,a,b,aa,ab,ba,bb,例2，正规式(a)| (b),*,(c)它所表示的正规集为：,根据运算符的优先级，上述正规式可以表示成 a|b,*,c；,a|b,*,c所表示的正规集为：串a或者是由零个或多个b后跟一个c 形成的字符串的集合。,或写成L(a|b,*,c)=a b,n,c | 其中n是大于或等于0的整数,每一种程序设计语言都有自己的字符集(字母表),。,语言中的各个,单词,或是,上的单个字符,(如运算符、分隔符等)，或是,上的字符串,(如常数、表示符和关键字等)。,程序设计语言的单词可用正规式来定义，由正规式描述的正规集即为程序设计语言的单词类。例如：,C-,语言的词法,正规表达式,是表示模式的一种重要方法，每个模式匹配一个字符串集合(即正规集)。,正规集,是正规表达式所定义的语言。,正规表达式,可以作为字符串集合(即正规集)的名字。,给定一个正规式,它唯一确定一个正规集；反之不成立。即一个正规集可由多个不同的正规式表示。,aa,a,aa, aaa,任意个a的串,a|aa,a,aa, aaa,任意个a的串,例如：,Compiler,编 译 原 理,Wednesday, March 13, 2013,正规式与,有穷自动机的等价性,（1）对于字母表上的NFA M，可以构造一个上的正规式R，使得L(R)=L(M)；,（2）对于字母表上的每个正规式R，可以构造一个上的NFA M，使得L(M)=L(R)。,Compiler,编 译 原 理,Wednesday, March 13, 2013,1. NFA M,正规式R,(1)在,M,上加两个结点S,Z，从S结点用,弧到M的所有初态，从M的所有终态用到Z结成与M等价的M，M只有一个初态S和一个终态Z.,例:,M:,0,3,2,1,4,start,a,b,a,b,a,b,b,b,a,a,解:,(1)加S Z,S,0,3,4,1,2,Z,a,a,b,a,b,a,b,a,b,b,Compiler,编 译 原 理,Wednesday, March 13, 2013,(2)逐步消去M中的所有结点,直至剩下S和Z结点,在消结过程中,逐步用正规式来标记弧, 规则如下:,1,.对于 代之为,2,.,对于,代之为,3,.对于 代之为,R,1,R,2,1,2,3,3,1,R,1,R,2,1,2,2,1,R,2,R,1,R,2,R,1,|,R,1,R,3,1,2,3,3,1,R,1,R,2,R,3,R,2,Compiler,编 译 原 理,Wednesday, March 13, 2013,(2)消除M中的所有结点,a|b,x,0,2,4,y,aa,bb,a|b,a|b,x,0,y,aa(a|b) *,bb(a|b) *,a|b,解:,(1)加xy,x,0,3,4,1,2,y,a,a,b,a,b,a,b,a,b,b,x,y,(a|b)*(aa|bb)(a|b)*,Compiler,编 译 原 理,Wednesday, March 13, 2013,2.正规式R,NFA M,（1）对NFA M构造一个广义的状态图，其中只有一个初态S和终态Z，连接S和Z的有向弧标记为正规式。,（2）对正规式依次进行分解，分解的过程是一个不断加入结点和弧的过程，直到转换图上的所有弧标记上都是字母表上的元素或,为止。,Compiler,编 译 原 理,Wednesday, March 13, 2013,若s,t为上的正规式,(a)对于正规式R=st,x,y,st,x,y,s,t,t,(b)对于正规式R=s|t,x,y,s|t,x,y,s,t,(c)对于正规式R=rs,*,t,x,y,rs,*,t,x,y,r,t,t,s,Compiler,编 译 原 理,Wednesday, March 13, 2013,A,Z,S,(a|b) *,abb,例:为R=(a|b) abb构造NFA,使得L(N)=L(R),*,S,Z,b,a,b,A,B,b,a,Z,bb,S,a|b,A,a,Compiler,编 译 原 理,Wednesday, March 13, 2013,1.正规文法,正规式,规则1,规则2,规则3,文法产生式,正规式,AxB,By,AxA|y,Ax,Ay,A=xy,A=x,*,y,A=x|y,步骤1 将每条产生式改写为正规式；,步骤2 用代入法解正规式方程组，最后只剩下一个开始符号定义的正规式，其中不含非终结符。,正规文法与正规式,Compiler,编 译 原 理,Wednesday, March 13, 2013,【例3.5】,GS:,SaA|a AdA|d,规则1,规则2,规则3,文法产生式,正规式,AxB,By,AxA|y,Ax,Ay,A=xy,A=x,*,y,A=x|y,S=aA|a,A= d*d,代入:S=ad*d|a ad*,Compiler,编 译 原 理,Wednesday, March 13, 2013,2.正规式,正规文法,步骤1 构造 Sr,步骤2 不断利用表3.4的规则做变换,直到每个产生式最多含有一个终结符为止,规则1,规则2,规则3,文法产生式,正规式,AxB,By,AxA|y,Ax,Ay,A=xy,A=x,*,y,A=x|y,Compiler,编 译 原 理,Wednesday, March 13, 2013,【例3.6】求正规式(a|b)(a|b|0|1)*对应的正规文法,S(a|b)(a|b|0|1)*,S(a|b),AaA|bA|0A|1A|,GS：,SaA|bA,AaA|bA|0A|1A|,A(a|b|0|1)*,Compiler,编 译 原 理,Wednesday, March 13, 2013,正规文法,NFA,正规式,6,5,4,3,1,2,DFA,最小化,整体框架,8,7,Compiler,编 译 原 理,Wednesday, March 13, 2013,词法规则 状态图 词法分析程序,词法分析程序的实现,（1）根据词法规则写出正规文法；,（2）将正规文法转换成状态图；,（3）将状态图转换成流程图。,Compiler,编 译 原 理,Wednesday, March 13, 2013,（1）根据词法规则写出正规文法,字母 | 字母 | 数字）,数字 | 数字,+ | * | |, | ;,=,Compiler,编 译 原 理,Wednesday, March 13, 2013,【例3.3】使用正规式来表示例3.2中的相应单词符号。,字母 | 字母 | 数字）,数字 | 数字,+ | * | |, | ;,=,标识符： l(l|d) *,无符号整数： dd*,单界符： + | * | |, | ;,双界符： =,Compiler,编 译 原 理,Wednesday, March 13, 2013,标识符,出口,S,1,非字母数字,字母,字母、数字,无符号整数,出口,S,2,非数字,数字,数字,单字符分界符,出口,S,3,其他字符,+ * =, ;,双字符分界符,出口,S,4,其他字符,5,=,非 =,字母 | 字母 | 数字）,数字 | 数字,+ | * | |, | ;,=,（2）将正规文法转换成状态图,Compiler,编 译 原 理,Wednesday, March 13, 2013,合并, 将初始状态合并为一个唯一的初态；, 化简调整状态冲突并对冲突状态重新编号；, 如有必要，增加出错状态。,Compiler,编 译 原 理,Wednesday, March 13, 2013,标识符,无符号整数,单界符,双界符,S,1,非字母数字,字母,字母、数字,2,非数字,数字,数字,3,其他字符,+ * ，,（ ）,出口,4,其他字符,5,=,非 =,出错,其他,读字符,查保留字表,返回S,合并后的状态图,Compiler,编 译 原 理,Wednesday, March 13, 2013,（3）将状态图转换成流程图，如图3.5,写出词法分析程序,