自动机与形式语言第三章epsilon-NFA课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,2024/9/16,1,RG,RE,-NFA,NFA,DFA,正则语言,(RL),2024/9/16,2,3.4,带空移动的有穷状态自动机,接受语言,0,n,1,m,2,k,|n,，,m,，,k0,的,NFA,3,允许带,输入,的状态跳转,这些状态跳转可以同时进行，无需输入字符,方便构造，更加“智能”，但也,只接收,RL,3.4,带空移动的有穷状态自动机,2024/9/16,4,3.4,带空移动的有穷状态自动机,接受语言,0,n,1,m,2,k,|n,，,m,，,k0,的,NFA,是否可以构造成下图所示的“,-NFA,”,？,其构造显然比图,1-13,所示的,NFA,更容易。当然还希望它们是等价的。,5,例子,:,-NFA,C,E,F,A,B,D,1,1,1,0,0,0,0 1,A E B,B,C D,C,D,D, ,E F,B, C,F D, ,*,2024/9/16,6,3.4,带空移动的有穷状态自动机,带空移动的不确定的有穷状态自动机,(non-deterministic finite automaton with -moves,-NFA),M=(Q,，,，,q,0,，,F),，,Q,、,q,0,、,F,的意义同,DFA,。,：,Q(),2,Q,2024/9/16,7,3.4,带空移动的有穷状态自动机,非空移动,(q,，,a)Q,(q,，,a)= p,1,，,p,2,，,，,p,m,表示,M,在状态,q,读入字符,a,，可以选择地将状态变成,p,1,、,p,2,、,或者,p,m,，并将读头向右移动一个带方格而指向输入字符串的下一个字符。,2024/9/16,8,3.4,带空移动的有穷状态自动机,空移动,qQ,(q,，,)= p,1,，,p,2,，,，,p,m,表示,M,在状态,q,不读入任何字符，可以选择地将状态变成,p,1,、,p,2,、,或者,p,m,。也可以叫做,M,在状态,q,做一个空移动,(,又可以称为,移动,),，并且选择地将状态变成,p,1,、,p,2,、,或者,p,m,。,9,-NFA,状态的闭包,-CLOSURE(q),=,从状态,q,出发，跟随,标记的弧所能到达的状态的集合,。,例,:,-CLOSURE(A)= A;,-CLOSURE(E)= B, C, D, E.,状态集合的闭包,-CLOSURE(P),=,集合,P,中所有元素的,闭包的集合,例,: -CLOSURE(A,E)= A,B,C,D,E;,C,E,F,A,B,D,1,1,1,0,0,0,2024/9/16,10,3.4,带空移动的有穷状态自动机,-CLOSURE(q)=p|,从,q,到,p,有一条标记为,的路,。,11,拓展的,基础,: (q,) =,-CLOSURE,(q).,归纳,: (q, wa),计算为：,从,(q, w) = S,出发；,对于,S,中所有元素,p,，计算,-CLOSURE,(,(p, a),的并集。,结论,: (q, w),是从,q,出发，沿着标记为,w,的路径所有能到达的状态的集合。,2024/9/16,12,3.4,带空移动的有穷状态自动机,13,例子,:,拓展的,(A,) =,-CLOSURE,(A) = A.,(A, 0) =,-CLOSURE,(E) = B, C, D, E.,(A, 01) =,-CLOSURE,(C, D) = C, D.,-NFA,的,语言,是所有,w,的集合，,(q,0, w),包含接受状态。,C,E,F,A,B,D,1,1,1,0,0,0,2024/9/16,14,3.4,带空移动的有穷状态自动机,对任意,(P,，,a),2,Q,。,2024/9/16,15,3.4,带空移动的有穷状态自动机,在,-NFA,中，对任意,a,，,q,Q,，,需要严格区分。,2024/9/16,16,状态,0,1,2,0,1,2,q,0, q,1, q,0,q,0,q,1,q,2,q,2,q,1, q,2, q,1,q,1,q,2,q,2,q,2, q,2,q,2,q,2,q,0,q,1,q,2,q,1,q,2,q,1,q,2,2024/9/16,17,3.4,带空移动的有穷状态自动机,M,接受,(,识别,),的语言,对于,x,*,，仅当,时，称,x,被,M,接受。,18,NFA,-NFA,等价,所有,NFA,都是,-NFA,.,仅仅不包含带,的状态转换,要证明等价性，需证明对于任意的,-NFA,，能构建一个接收相同语言的,NFA,方法：把,transition,跟“真实”的状态转换结合起来,19,消除,-Transition,接受,w,后,a,a,a,跳转,状态,q,(q,wa,) =,-CLOSURE,( ),p1,p2,pn,P,a,2024/9/16,20,3.4,带空移动的有穷状态自动机,定理,3-2,-NFA,与,NFA,等价。,证明：设有,-NFA,M,1,=(Q,，,1,，,q,0,，,F),(1),构造与之等价的,NFA M,2,。,取,NFA,M,2,=(Q,，,2,，,q,0,，,F,2,),Fq,0,如果,F-CLOSURE(q,0,),F,2,=,F,如果,F,-CLOSURE(q,0,)=,2024/9/16,21,3.4,带空移动的有穷状态自动机,与上图,-NFA,等价的,NFA,。,2024/9/16,22,3.5 FA,是正则语言的识别器,3.5.1 FA,与右线性文法,DFA M=(Q,，,，,q,0,，,F),，处理句子,a,1,a,2,a,n,的特性。,M,按照句子,a,1,a,2,a,n,中字符的出现顺序，从开始状态,q,0,开始，依次处理字符,a,1,、,a,2,、,、,a,n,，在这个处理过程中，每处理一的字符进入一个状态，最后停止在某个终止状态。,2024/9/16,23,3.5.1 FA,与右线性文法,它每次处理且仅处理一个字符：第,i,步处理输入字符,a,i,。,对应于使用,(q,，,a)=p,的状态转移函数的处理，相当于是在状态,q,完成对,a,的处理，然后由,p,接下去实现对后续字符的处理。,当,(q,，,a)=p,F,，且,a,是输入串的最后一个字符时，,M,完成对此输入串的处理。,2024/9/16,24,3.5.1 FA,与右线性文法,A,0,a,1,A,1,对应产生式,A,0,a,1,A,1,a,1,a,2,A,2,对应产生式,A,1,a,2,A,2,a,1,a,2,a,n-1,A,n-1,对应产生式,A,n-2,a,n-1,A,n-1,a,1,a,2,a,n-1,a,n,对应产生式,A,n-1,a,n,2024/9/16,25,3.5.1 FA,与右线性文法,q,0,a,1,a,2,a,n-1,a,n,a,1,q,1,a,2,a,n-1,a,n,对应,(q,0,，,a,1,)=q,1,a,1,a,2,q,2,a,n-1,a,n,对应,(q,1,，,a,2,)=q,2,a,1,a,2,a,n-1,q,n-1,a,n,对应,(q,n-2,，,a,n-1,)=q,n-1,a,1,a,2,a,n-1,a,n,q,n,对应,(q,n-1,，,a,n,)=q,n,2024/9/16,26,3.5.1 FA,与右线性文法,其中,q,n,为,M,的终止状态。考虑根据,a,1,、,a,2,、,、,a,n,，让,A,0,与,q,0,对应、,A,1,与,q,1,对应、,A,2,与,q,2,对应、,、,A,n-2,与,q,n-2,对应、,A,n-1,与,q,n-1,对应。这样，就有希望得到满足定理,2-4-1,的正则文法的推导与,DFA,的互相模拟的方式。,2024/9/16,27,3.5.1 FA,与右线性文法,定理,3-3,FA,接受的语言是正则语言。,证明：,(1),构造。,基本思想是让,RG,的派生对应,DFA,的移动。,设,DFA M=(Q,，,，,q,0,，,F),，,取右线性文法,G=(Q,，,P,，,q,0,),，,P=q,ap|(q,，,a)=pq,a|(q,，,a)=pF,2024/9/16,28,3.5.1 FA,与右线性文法,（,2,）,证明,L(G)=L(M)-,。,对于,a,1,a,2,a,n-1,a,n,+,，,q,0,+,a,1,a,2,a,n-1,a,n,q,0,a,1,q,1,，,q,1,a,2,q,2,，,，,q,n-2,a,n-1,q,n-1,，,q,n-1,a,n,P,(q,0,，,a,1,)=q,1,，,(q,1,，,a,2,)=q,2,，,，,(q,n-2,，,a,n-1,)=q,n-1,，,(q,n-1,，,a,n,)=q,n,，且,q,n,F,(q,0,，,a,1,a,2,a,n-1,a,n,)= q,n,F,a,1,a,2,a,n-1,a,n,L(M),2024/9/16,29,3.5.1 FA,与右线性文法,（,3,）,关于,句子。,如果,q,0,F,，则,L(M),，,L(G)=L(M),。,如果,q,0,F,，则由定理,2-6,和定理,2-7,，存在正则文法,G,，使得,L(G)=L(G) =L(M),。,综上所述，对于任意,DFA M,，存在正则文法,G,，使得,L(G)=L(M),。,定理得证。,2024/9/16,30,3.5.1 FA,与右线性文法,例：,与下图所给,DFA,等价的正则文法,q,s,0|0q,0,|1q,1,q,0,0|0q,0,|1q,1,q,1,0q,2,|1|1q,0,q,2,0q,1,|1q,2,2024/9/16,31,3.5.1 FA,与右线性文法,例：,与下图所给的,DFA,等价的正则文法,q,0,0q,1,|1q,t,|2q,t,q,1,0q,1,|1q,2,|2q,t,q,2,0q,t,|1q,2,|2q,3,|2,q,3,0q,t,|1q,t,|2q,3,|2,q,t,0q,t,|1q,t,|2q,t,2024/9/16,32,3.5.1 FA,与右线性文法,定理,3-4,正则语言可以由,FA,接受。,证明：,（,1,）构造。,基本思想：让,FA,模拟,RG,的派生。,设,G=(V,，,T,，,P,，,S),，且,L(G),，,取,FA M=( VZ,，,T,，,，,S,，,Z),，,Z,V,。,2024/9/16,33,3.5.1 FA,与右线性文法,对,(a,，,A)TV,B|A,aBPZ,如果,A,aP,(A,，,a)=,B|A,aBP,如果,A,a,P,用,B(A,，,a),与产生式,A,aB,对应,用,Z(A,，,a),与产生式,A,a,对应。,2024/9/16,34,3.5.1 FA,与右线性文法,（,2,）,证明,L(M)=L(G),对于,a,1,a,2,a,n-1,a,n,T,+,，,a,1,a,2,a,n-1,a,n,L(G),S,+,a,1,a,2,a,n-1,a,n,S,a,1,A,1,a,1,a,2,A,2,a,1,a,2,a,n-1,A,n-1,a,1,a,2,a,n-1,a,n,S,a,1,A,1,，,A,1,a,2,A,2,，,，,A,n-2,a,n-1,A,n-1,，,A,n-1,a,n,P,2024/9/16,35,3.5.1 FA,与右线性文法,A,1,(S,，,a,1,),，,A,2,(A,1,，,a,2,),，,，,A,n-1,(A,n-2,，,a,n-1,),，,Z(A,n-1,，,a,n,),Z(S,，,a,1,a,2,a,n-1,a,n,),a,1,a,2,a,n-1,a,n,L(M),对于,，按照定理,2-5,和定理,2-6,处理。,2024/9/16,36,3.5.1 FA,与右线性文法,例,3-10,构造与所给正则文法等价的,FA,：,G,1,：,E,0A|1B,A,1|1C,B,0|0C,C,0B|1A,2024/9/16,37,3.5.1 FA,与右线性文法,(E,，,0)=A,对应,E,0A,(E,，,1)=B,对应,E,1B,(A,，,1)=Z,C,对应,A,1|1C,(B,，,0)=Z,C,对应,B,0|0C,(C,，,0)=B,对应,C,0B,(C,，,1)=A,对应,C,1A,2024/9/16,38,3.5.1 FA,与右线性文法,2024/9/16,39,3.5.1 FA,与右线性文法,推论,3-1,FA,与正则文法等价。,证明：根据定理,3-3,和定理,3-4,即可得到。,2024/9/16,40,3.5.1 FA,与左线性文法,按照推导来说，句子,a,1,a,2,a,n-1,a,n,中的字符被推导出的先后顺序正好与它们在句子中出现的顺序相反；而按照归约来看，它们被归约成语法变量的顺序则正好与它们在句子中出现的顺序相同：,a,1,，,a,2,，,，,a,n-1,，,a,n,。可见，归约过程与,FA,处理句子字符的顺序是一致的，所以可考虑依照,“,归约,”,来研究,FA,的构造。,2024/9/16,41,3.5.1 FA,与左线性文法,对于形如,A,a,的产生式：在推导中，一旦使用了这样的产生式，句型就变成了句子，而且,a,是该句子的第一个字符；按,“,归约,”,理解，对句子的第,1,个字符，根据形如,A,a,的产生式进行归约。对应到,FA,中，,FA,从开始状态出发，读到句子的第一个字符,a,，应将它,“,归约,”,为,A,。我们如果考虑用语法变量对应,FA,的状态，那么，此时我们需要引入一个开始状态，比如说：,Z,。这样，对应形如,A,a,的产生式，可以定义,A,(Z,，,a),。,2024/9/16,42,3.5.1 FA,与左线性文法,按照上面的分析，对应于形如,A,Ba,的产生式：,FA,应该在状态,B,读入,a,时，将状态转换到,A,。也可以理解为：在状态,B,，,FA,已经将当前句子的、处理过的前缀,“,归约,”,成了,B,，在此时它读入,a,时，要将,Ba,归约成,A,，因此，它进入状态,A,。,2024/9/16,43,3.5.1 FA,与左线性文法,按照,“,归约,”,的说法，如果一个句子是文法,G,产生的语言的合法句子，它最终应该被归约成文法,G,的开始符号。所以，,G,的开始符号对应的状态就是相应的,FA,的终止状态。,如何解决好开始符号只有一个，而,DFA,的终止状态可以有多个的问题。,2024/9/16,44,3.5.1 FA,与左线性文法,例如：对文法,G,2,：,E,A0|B1,A,1|C1,B,0|C0,C,B0|A1,对应,(A,，,0)=E,(B,，,1)=E,(Z,，,1)=A (C,，,1)=A,(Z,，,0)=B,(C,，,0)=B,(B,，,0)=C,(A,，,1)=C,2024/9/16,45,3.5.1 FA,与左线性文法,G,2,：,E,A0|B1,A,1|C1,B,0|C0,C,B0|A1,2024/9/16,46,3.5.1 FA,与左线性文法,定理,3-5,左线性文法与,FA,等价。,2024/9/16,47,3.6 FA,的一些变形,3.6.1,双向有穷状态自动机,确定的双向有穷状态自动机,(two-way deterministic finite automaton,，,2DFA),M=(Q,，,，,q,0,，,F),Q,、,q,0,、,F,的意义同,DFA,。,2024/9/16,48,3.6.1,双向有穷状态自动机,：,Q,Q,L,，,R,，,S,，对,(q,，,a),Q,如果,(q,，,a)= p,，,L,，它表示,M,在状态,q,读入字符,a,，将状态变成,p,，并将读头向左移动一个带方格而指向输入字符串的前一个字符。,如果,(q,，,a)= p,，,R,，它表示,M,在状态,q,读入字符,a,，将状态变成,p,，并将读头向右移动一个带方格而指向输入字符串中下一个字符。,如果,(q,，,a)= p,，,S,，它表示,M,在状态,q,读入字符,a,，将状态变成,p,，读头保持在原位不动。,2024/9/16,49,3.6.1,双向有穷状态自动机,M,接受的语言,L(M)=x| q,0,x,*,xp,且,p,F,是,2DFA,接受的语言。,定理,3-6,2DFA,与,FA,等价。,2024/9/16,50,3.6.1,双向有穷状态自动机,不确定的双向有穷状态自动机,(two-way nondeterministic finite automaton,，,2NFA),M=(Q,，,，,q,0,，,F),Q,、,q,0,、,F,的意义同,DFA,。,：,Q,2,Q,L,，,R,，,S,。,2024/9/16,51,3.6.1,双向有穷状态自动机,(q,，,a)= ( p,1,，,D,1,)( p,2,，,D,2,) ,，,(p,m,D,m,) ,表示,M,在状态,q,读入字符,a,，可以选择地将状态变成,p,1,同时按,D,1,实现对读头的移动、或者将状态变成,p,2,同时按,D,2,实现对读头的移动、,或者将状态变成,p,m,同时按,D,m,实现对读头的移动。其中,D,1,，,D,2,，,，,D,m,L,，,R,，,S,，表示的意义与,2DFA,的定义表示的意义相同,。,2024/9/16,52,3.6.1,双向有穷状态自动机,定理,3-7,2NFA,与,FA,等价。,2024/9/16,53,3.6.2,带输出的,FA,Moore,机,M=(Q,，,，,，,，,q,0,),Q,、,q,0,、,的意义同,DFA,。,输出字母表,(output alphabet),。,：,Q,为输出函数。对,q,Q,，,(q)=a,表示,M,在状态,q,时输出,a,。,2024/9/16,54,3.6.2,带输出的,FA,对于,a,1,a,2,a,n-1,a,n,*,，如果,(q,0,，,a,1,)=q,1,，,(q,1,，,a,2,)=q,2,，,，,(q,n-2,，,a,n-1,)=q,n-1,，,(q,n-1,，,a,n,)=q,n,，,则,M,的输出为,(q,0,),(q,1,) ,(q,n-1,),2024/9/16,55,3.6.2,带输出的,FA,Mealy,机,M=(Q,，,，,，,，,q,0,),输出字母表。,：,Q,为输出函数。对,(q,，,a),Q,，,(q,，,a)=d,表示,M,在状态,q,读入字符,a,时输出,d,。,2024/9/16,56,3.6.2,带输出的,FA,对于,a,1,a,2,a,n-1,a,n,*,，,M,的输出串为：,(q,0,a,1,),(,(q,0,a,1,),a,2,) ,(,(,(q,0,，,a,1,),a,2,),a,n,),设,(q,0,，,a,1,)=q,1,，,(q,1,，,a,2,)=q,2,，,，,(q,n-2,，,a,n-1,)=q,n-1,，,(q,n-1,，,a,n,)=q,n,，,则,M,的输出可以表示成：,(q,0,，,a,1,),(q,1,，,a,2,) ,(q,n-1,，,a,n,),2024/9/16,57,3.6.2,带输出的,FA,Moore,机处理该串时每经过一个状态，就输出一个字符：输出字符和状态一一对应；,Mealy,机处理该串时的每一个移动输出一个字符：输出字符和移动一一对应。,2024/9/16,58,3.6.2,带输出的,FA,定理,3-8,Moore,机与,Mealy,机等价,。,2024/9/16,59,3.7,小结,本章讨论正则语言的识别器,FA,。包括,DFA,、,NFA,、,-NFA,。,RG,与,FA,的等价性。简单介绍带输出的,FA,和双向,FA,。,FA M,是一个五元组，,M=(Q,，,，,q,0,，,F),，它可以用状态转移图表示。,M,接受的语言为,x| x,*,且,(q,，,x),F,。如果,L(M,1,)=L(M,2,),，则称,M,1,与,M,2,等价。,FA,的状态具有有穷的存储功能。这一特性可以用来构造接受一个给定语言的,FA,。,2024/9/16,60,3.7,小结,NFA,允许,M,在一个状态下读入一个字符时选择地进入某一个状态，对于,x,*,，如果,(q,0,，,x),F,，则称,x,被,M,接受，如果,(q,0,，,x),F=,，则称,M,不接受,x,。,M,接受的语言,L(M)=x| x,*,且,(q,0,，,x),F,。,2024/9/16,61,3.7,小结,-NFA,是在,NFA,的基础上，允许直接根据当前状态变换到新的状态而不考虑输入带上的符号。对,q,Q,，,(q,，,)= p,1,，,p,2,，,，,p,m,表示,M,在状态,q,不读入任何字符，可以选择地将状态变成,p,1,、,p,2,、,或者,p,m,。这叫做,M,在状态,q,做一个空移动。,NFA,与,DFA,等价，,-NFA,与,NFA,等价，统称它们为,FA,。,2024/9/16,62,3.7,小结,根据需要，可以在,FA,中设置一种特殊的状态,陷阱状态。但是，不可达状态却是应该无条件地删除的。,FA,是正则语言的识别模型。分别按照对推导和归约的模拟，可以证明,FA,和左线性文法、右线性文法等价。,2024/9/16,63,3.7,小结,2DFA,是,FA,的又一种变形，它不仅允许读头向前移动，还允许读头向后移动。通过这种扩充，,2DFA,仍然与,FA,等价。,Moore,机和,Mealy,机是两种等价的带输出的,FA,，,Moore,机根据状态决定输出字符，,Mealy,机根据移动决定输出字符。,