有限自动机理论CH3PART2.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,.4,不确定的有限状态自动机,每个,FSL,都是,右线性语言,(,定理,3-1,),问题,每个,右线性语言,是不是一个,FSL,？,例,接收语言,aa,，,ab,的,FA,省略,陷阱状态,q,1,a,b,q,0,q,2,a,a,q,3,该自动机识别的语言,L=,aa,，,ab,是右线性语言；,但自动机,不是,DFA,。,(q,0,，,a)=,q,1,，,q,2,即没有到达确定的惟一的状态。,不确定的有限状态自动机,-,NFA,3.4.1,不确定的有限状态自动机,定义,3-10,NFA,是一个,五元式,，,NFA=,（,Q,，,，,Q,0,，,F,）,其中：,Q,是一个有限状态的集合,是字母表,Q,0,Q,是,开始状态集合,F,Q,是接收状态集合,是,Q,2,Q,的状态转换函数,即,(q,，,a),2,Q,NFA,在状态,q,，扫描字母,a,后到达,可能,的,下一,状态集合,。,NFA,与,DFA,NFA,有一个,可能的,开始状态集合,和可能的下一,状态集合,其余的同,DFA,。,NFA,与,DFA,的,重要,区别,在于,转移函数,的不同。,(q,，,x),对应,的是,状态的一个子集,FA,处于状态,q,DFA,对每个,字母,只有一个状态的转移。,NFA,对,某,个,字母,可以有,多个状态转移,；,NFA,接收该字母,时,从多个状态转移,中,非确定,地,选择,任意,一个,。,具体地,对于,NFA,，,(q,，,a),Q,(q,，,a),有,3,种可能,(q,，,a)=,(q,，,a)=,q,1,(q,，,a)=,q,1,，,q,2,，,，,q,n,或,或,(q,，,a),仍是一个,状态转换函数,，只是其,值域,发生了改变。,所有,(q,，,a),对应的所有子集元素个数都为,1,时，,NFA,退化为,DFA,NFA,停机,NFA,在两种情况下,自动停机,：,将输入串扫描结束,(q,，,a)=,(,即对应,没有定义,),或,在扫描一个串,w,时，,NFA,的状态发生转换，可能会有多种,情况：,可能在,接收状态,时终止；,可能在,非接收状态,时终止；,也可能在,中途停止,。,若,至少存在一条路径,可以使,NFA,在扫描串,w,后到达接收状态,则串,w,能被,NFA,所识别,。,对于字母表上的,NFA,，它能识别的所有串的集合，称为,NFA,能识别的语言。,记为,L(NFA),问题,如何形式化定义,L,(NFA),?,定义,3-11NFA,扩展状态转换函数,给定,NFA,，扩展的状态转换函数,*,：,2,Q,*,2,Q,为,*,(,p,，,w,)=Q,即,NFA,在状态集合,p,时，扫描串,w,后到达可能的的状态集合,Q,。,NFA,扩展状态转换函数,若,p=q,1,，,q,2,，,q,n,；,*,（,p,，,）,=p,a,*,(,p,，,a),=,(q,，,a)|qp,=(q,1,a),(q,2,a),(q,n,a),对于串,w,w=,a,*(p,，,w),=*(p,，,a,),=,(q,，,a)|,q,*(p,，,),或,w=,a,*,(,p,，,w,),=,*,(,p,，,a,),=,*,(,q,)|,q,*,(,p,，,a,),L(NFA),表示被,NFA,所接收的语言,L(NFA)=w|w,*,且,*,(Q,0,，,w),F,它表示所有串,w,的集合,在,NFA,的状态图中，,至少存在一条路径,以,w,为标记，能使,NFA,从某个开始状态到达某个接收状态。,3.4.2 NFA,的,确定化,DFA,可以转换为,NFA,NFA,可以转换为,DFA,(,确定化,),A,的,充分条件,为,B,A,的,必要条件,为,B,A,当且仅当,B,即,A,的,充要条件,为,B,B=,A,A=,B,定理,3-3,*,的一个子集,L,是一个,FSL,，,充要条件为,存在,NFA,，使得,L(NFA)=L,。,证明：,=,必要性,若,L,是,FSL,，,则有,L=L(DFA,）,DFA,=(Q,，,，,，,q,0,，,F),构造,NFA,=(Q,，,1,，,q,0,，,F),1,(q,，,a)=,(q,，,a),即把,DFA,的一个状态 当作,NFA,的一个状态集合,则,L=L(DFA)=L(NFA),证明,:0,NFA,状态转移图,q,0,0,1,0,1,2,2,q,1,q,2,q,3,或,q,0,0,1,0,1,2,2,q,1,q,2,q,3,例,3-27,构造,NFA,，识别,0,，,1,上的语言,L=,0,n,1,m,2,k,|,n,m,k=,0,0,1,0,1,2,2,q,3,q,0,q,1,q,2,2,1,2,或 多个开始状态的,NFA,1,0,2,2,q,3,q,1,q,2,1,2,3.5,带,动作的有限状态自动机,对于,FA,（,DFA,、,NFA,），有,(q,，,)=q,*,(q,，,)=q,*,(P,，,)=P,表示,FA,不读入任何字母,(,即只扫描空串时,),，,FA,的状态不发生改变，并且,读头不进行移动,，仍然指向当前非空字符。,若允许,FA,在不读入任何字符时,FA,的,状态可以发生改变,，,则,FA,为,带有,动作,的,FA,定义,3-14,带,动作的有限状态自动机,带有,动作的,FA,是一个五元式,-FA,=(Q,，,，,Q,0,，,F),Q,，,Q,0,，,F,的含义同,NFA,:Q,2,Q,(q,，,a),2,Q,(q,),2,Q,即,具体,(q,，,a)=,表示自动机在读入字母,a,后，自动机停机。,(,q,)=,q,表示自动机在状态,q,时，不读入任何字母，自动机状态不变,并且读头不移动；,(q,，,a,)=p,1,，,p,2,，,p,3,，,，,p,m,表示自动机在读入字母,a,后，自动机的状态可以,选择地,改变为,p,1,，,p,2,，,p,3,，,，或者,p,m,并将读头向右移动一个单元；,(q,)=q,1,，,q,2,，,q,3,，,，,q,n,表示自动机在状态,q,时，不读入任何字母，自动机的状态可以,选择地,改变为,q,1,，,q,2,，,q,3,，,，或,q,n,并且读头不移动；,注意,带有,动作的,FA,一定,是,NFA,。,一般，记为,-NFA,。,例,3-28,使用,-NFA,接收语言,L=0,*,1,*,2,*,即,L=,0,n,1,m,2,k,|n,m,k=,0,状态图,0,*,1,*,2,*,q,0,q,1,q,2,2,0,1,对应的,5,个,函数为：,(q,0,，,0)=q,0,(q,0,，,)=q,1,(q,1,，,1)=q,1,(q,1,，,)=q,2,(q,2,，,2)=q,2,定义,3-15,对于,-NFA,，,q,Q,从,q,开始,，,扫描,1,个或多个,后能够到达的状态集记为,-CLOSURE(q,),。,-CLOSURE(q,),=p|,从,q,到,p,有标记,全是,的有 向路,对于,-NFA,，,q,Q,-CLOSURE,(,q,),是由递归规则,确定,的状态集：,规则,(1)q,-CLOSURE(q,),即任意状态,q,接收空串,，,至少,都能,保持状态,q,不变；,规则,(2),如果,p,-CLOSURE(q,),则,(p,),-CLOSURE(q,),(3),重复,(2),，直到,-CLOSURE(q,),中的状态不再增加为止。,注意,-CLOSURE(q,),与,(q,),不同,进一步,对于,状态集合,P,，定义,-CLOSURE(P),=,qP,-CLOSURE,（,q,）,定义,3-16,扩展的状态转换函数,-NFA,扩展状态转换函数,*,：,2,Q,*,2,Q,为,*,（,P,，,w,）,=Q,即自动机在状态集合,P,时，扫描串,w,后到达的状态集合,Q,。,空串,*,(,P,)=-CLOSURE(,P,),*,(,q,)=,-CLOSURE(,q,),*,(,q,)=,?,单个字母,*,(P,，,a,)=,*,(q,，,a,),*,(q,，,a,)=,*,(q,，,a,),=-CLOSURE(P),=,-CLOSURE,(,(,p,a,),qP,p,*(,q,),对于串,w,a,*,(,P,wa,)=,*,(,*,(,P,w),a,),或,*,(,P,aw,)=,*,(,*,(,P,a),w,),对于,-CLOSURE(q,0,)=,-CLOSURE(q,1,)=,-CLOSURE(q,2,)=,q,0,q,1,q,2,2,0,1,q,0,q,1,，,q,2,q,2,q,1,q,2,对于,*,(q,0,),=-CLOSURE(q,0,),=q,0,，,q,1,，,q,2,q,0,q,1,q,2,2,0,1,*,(q,0,0),=,*,(q,0,0,),=,-CLOSURE,(,(p,0),p,*(,q,0,),=,-CLOSURE(,(q,0,0),(q,1,0),(q,2,0),=-CLOSURE(q,0,),=q,0,，,q,1,，,q,2,q,0,q,1,q,2,2,0,1,*,（,q,0,01,）,=,*,(,*,(q,0,0),1),=,*,(q,0,q,1,q,2,1),=,-CLOSURE(,(q,0,1),(q,1,1),(q,2,1),=,q,1,q,2,q,0,q,1,q,2,2,0,1,注意,*,(q,，,),与,(q,，,),不同,定理,3-5,如果语言,L,被,-NFA,接收，则,该语言,L,也能够被一个,NFA,接收,证明：,假设语言,L,被一个,-NFA,接收,-NFA,=(Q,，,，,Q,0,，,F),1),构造,NFA,1,=(Q,，,1,，,Q,0,，,F,1,),其中,:,对于,a,1,(q,，,a)=,*,（,q,，,a,）,F,1,=,F,q,0,若,F-CLOSURE(q,0,),F,1,=,F,若,F-CLOSURE(q,0,)=,2,）,证明对于,w,+,有,1,(q,0,，,w)=,*,（,q,0,w,）,过程自学,结论,如果语言,L,被,-NFA,接收，则语言,L,也能够被一个,NFA,接收,例,3-29,将,-NFA,改造为等价的,NFA,。,q,0,q,1,q,2,2,0,1,q,1,q,0,q,2,2,0,1,0,1,1,2,0,1,2,例,3-30,构造,-NFA,识别,0,，,1,上的语言,L=,0,k,|k=0,，,k,能够被,2,或,3,整除,即,L=,0,2n,或,0,3m,|,n,m,=0,q,0,q,1,q,3,q,2,q,4,q,5,0,0,0,0,0,思考,L=,0,2n+3m,|,n,m,0,请,验证,q,0,q,5,q,1,0,q,2,0,q,3,0,q,4,0,0,0,0,思考：,-NFA,转换为,NFA,能否,先将,-NFA,转换为,“,右线性,”,文法，再转换为,NFA,？,引进单产生式,A,B,3.6,有限状态自动机的一些,变形,有限状态自动机存在变形。,3.6.1,双向的有限状态自动机,在处理输入串的过程中，,双向的有限状态自动机的,读头,可以,向右,移动一个单元；,也可以,向左,移动一个单元；,也可以,不移动,。,定义,3-18,确定的双向的有限状态自动机,(,2DFA,),是一个五元式：,2DFA=,（,Q,，,，,q,0,，,F,）,其中，,Q,q,0,，,F,的含义同,DFA,：,状态转换函数；,QQ,L,，,R,，,N,对于,qQ,，,a,(q,，,a)=p,，,D,2DFA,在状态,q,读入字母,a,自动机状态将变为,p,状态,D=L,读头向左移动一个单元,D=R,读头向左移动一个单元,D=N,读头位置不变；,2DFA,格局,描述同,DFA,2DFA=,（,Q,，,，,q,0,，,F,）接收的语言为,L(2DFA),L(2DFA)=w|,q,0,w,=,*,q,，,qF,定理,3-6,2DFA,与,DFA,等价,。,证明：,略。,可以定义,不确定的双向的有限状态自动机,。,定义,3-20,不确定双向有限状态自动机,2NFA,是一个五元式：,2NFA=(Q,，,，,Q,0,，,F),其中,Q,，,Q,0,，,F,的含义同,NFA,：状态转换函数；,：,Q2,Q,L,，,R,，,N,对于,qQ,，,a,D,1,，,D,2,，,，,D,m,L,R,N,，,(q,a,)=(p,1,D,1,),(,p,2,D,2,),(,p,m,D,m,),2NFA,在状态,q,读入字母,a,可以将状态变为,p,i,按照,D,i,实现对读头的移动,定理,3-7,2NFA,与,NFA,等价。,证明：,略。,3.6.2,带输出的有限状态自动机,FA,，对于某个输入串,w,得到的结论是,:,是否接收该串,；,或,FA,输出,“是”或“否”,。,存在许多有穷状态系统,对于不同的输入信号，,除系统内部的状态变化之外，,还向,系统外部,输出各种信号,。,模型图,有限状态系统,输入序列,输入序列,典型带输出的有穷自动机,-,Moore,机和,Mealy,机。,由于它们带有输出，从抽象的角度考虑，就,没有,必要再设置,接收状态,（集）。,定义,3-21,Moore,机是一个,六元式,：,Moore M=(,Q,q,0,),其中,Q,，,q,0,，,的含义同,FA,：输出字母表,输出函数,：,Q,对于,qQ,，,a,(q,)=a,表示,Moore,机处于状态,q,时输出,a,Moore,机,在读入输入串的过程中,状态不断发生改变,并且,在每个状态上都有输出,对于输入串,a,1,a,2,a,3,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,则,Moore,机的输出序列可以表示为：,(q,0,)(q,1,)(q,2,),(q,n,),如果输入串的长度为,n,则,Moore,机的输出串的长度为,n+1,。,实际上,FA,只是,Moore,机的一个,特例,。,若,Moore,机的输出仅只有,F,或,T,将输出,T,的状态当作接收状态，,Moore,机就是一般的,FA,。,例,3-31,设计,Moore,机,=0,，,1,若将输入串当作二进制数，则在读入串的过程中，,希望输出已经读过的（数字）串模,3,的余数。,分析,模,3,的余数只能是,0,、,1,和,2,输出字母表,=0,，,1,，,2,状态,q,0,、,q,1,和,q,2,对应,3,种余数,状态上的标记表示,Moore,机在该状态时的输出,q,0,q,1,q,2,0,1,2,0,0,0,1,1,1,当输入为,1010,时,状态变换的序列为,q,0,q,1,q,2,q,2,q,1,输出,0 1 2 2 1,即,当输入,时，输出余数,0,当输入,1,时，输出余数,1,当输入,10,时，输出余数,2,当输入,101,时，输出余数,2,当输入,1010,时，输出余数,1,定义,3-22,Mealy,机是一个六元式：,Mealy M=(,Q,，,q,0,),其中,Q,，,q,0,，,的含义同,FA,：,输出字母表,输出函数,：,Q,对于,qQ,，,x,，,a,(q,，,x)=a,表示,Moore,机在状态,q,读入字母,x,时，输出,a,Mealy,机在读入输入串的过程中，,状态不断发生改变，,并且在读入某个字母时，,Mealy,机都有输出。,对于输入序列,a,1,a,2,a,3,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,则,Mealy,机的输出序列表示为：,(q,0,a,1,)(q,1,a,2,)(q,n-1,a,n,),若输入串的长度为,n,Mealy,机输出串的长度为,n,Moore,机输出串的长度为,n+1,例,3-32,对于语言,(0+1),*,(00+11),设计输出符号为,y,n,的,Mealy,机,读过的子串是句子,Mealy,机输出,y,表示接收；,读过的输入串不是句子,Mealy,机输出,n,表示拒绝。,若,(p,a,)=q,(p,a,)=b,则 状态,p,到,q,的有向边标记,a/b,Mealy,机,输入串是,01100,Mealy,机对应的输出为,nnyny,输入,0,拒绝；,01,拒绝；,011,接收,0110,拒绝；,01100,接收,一般地，,Mealy,机比一般的有限状态自动机具有,更强,的功效。,根据,Moore,机和,Mealy,机的定义，可知：对于输入串的序列,a,1,a,2,a,3,a,n-1,a,n,*,，,1)Moore,机处理该串时,每经过一个状态，就输出一个字符；,输出字符和,状态,一一对应,。,2)Mealy,机处理该串时,每一个,状态移动,，就输出一个字符；,输出字符和,转换,一一对应,。,Moore,机和,Mealy,机等价,设,Moore,机：,M,1,=(Q,1,，,1,1,q,01,),Mealy,机：,M,2,=(Q,2,，,2,2,q,02,),对于输入串,w,*,，若,T,1,(w)=,1,(q,01,)T,2,(w),称,Moore,机和,Mealy,机是等价的。,其中,T,1,(w),和,T,2,(w),分别表示,Moore,机,M,1,和,Mealy,机,M,2,关于输入串,w,的输出。,给定任意的,Moore,机，可以构造出与之等价的,Mealy,机；,给定任意的,Mealy,机，也可以构造出与之等价的,Moore,机。,定理,3-8,M,o,=(Q,1,q,0,),是个,Moore,机，,则有一个,Mealy,机,M,e,与之等价。,证明,设,Moore,机,M,o,=,（,Q,，,，,1,q,0,）,构造,Mealy,机,M,e,=,（,Q,，,，,2,q,0,）,其中,:,2,(q,，,a)=,1,(q,，,a),M,e,与,M,o,具有相同状态和,函数,对于相同的输入串序列,M,e,与,M,o,状态转换序列相同,惟一不同的只是将,M,o,的输出,前移一步,(,删除,q,0,对应的输出,),。,M,o,M,e,q,p,q,p,a,b,a/b,在不考虑,M,o,第一个输出符号的情况下，,M,e,与,M,o,的输出序列一定相同。证毕。,定理,3-9,M,1,=(Q,，,1,，,1,q,0,),是一个,Mealy,机，,则有一个,Moore,机,M,2,与之等价。,证明,思路：,只需要增加一个关于,q,0,的输出。,定理,3-10,Moore,机与,Mealy,机等价。,证明：,根据,定理,3-8,、定理,3-9,。,3.7,有限状态自动机的存储技术,FA,的有限状态控制器（,FSC,）可以保存有限数量的信息，即保存多个状态。,可以使用,n,元组,表示,一个状态,而,n,元组的不同的分量可以代表不同的含义。,最简单是使用二元组表示,第一个分量表示原来的状态,第二个分量是需要,存储,的信息,一个分量实现,控制,一个分量实现,存储,该技术也适合,下推自动机,和,图灵机,。,例,3-34,构造,FA,识别,a,，,b,，,c,上语言,L,该语言的每个句子的,第一个,符号在该句子中仅仅出现,一次,。,存储第一个字符,(start,，,a)=q,，,a,(start,，,b)=q,，,b,(start,，,c)=q,，,c,扫描,(,q,，,a,，,b,)=q,，,a,(,q,，,a,，,c,)=q,，,a,(q,，,b,，,a,)=q,，,b,(q,，,b,，,c,)=q,，,b,(q,，,c,，,a,)=q,，,c,(q,，,c,，,b,)=q,，,c,其中,start,是开始状态,q,，,a,、,q,，,a,和,q,，,c,是接收状态,有限状态自动机的基本结构和模型,并没有改变,但使用,n,元组表示一个状态更为,直观和方便,。,思 考：,构造,FA,接收,最后一个字符仅出现一次的语言,其中，,=a,，,b,，,c,提示：需要,存储,的信息是,？,