第3章 有穷自动机.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,有穷自动机形式定义,NFA,DFA,的转换,正规文法与有穷自动机,正规表达式与,FA,DFA,在计算机中的表示,小结,第3章有穷自动机,有穷自动机,DFA,定义,：,一个确定的有穷自动机（,DFA）M,是一个五元组：,M=（Q，t，q,0,，F,）,其中,1,Q,是一个有穷集，它,的每个元素,称,为,一个,状态,；,2,是,一个有穷字母表，它的每个元素称为一个输入符号，所以也称,为,输入符号字母表,；,3,t,是转换函数,，是在,Q,Q,上的映射，即，如,t（,qi,，a）=,qj,，（,qi,，,qj,Q就意味着，当前状态为,q,i,，,输入符为,a,时，将转换为下一个状态,qj,，,我们把,qj,称作,qi,的一个后继状态；,4,q,0,Q,是唯一,的一个,初态,；,5,F,Q,是,一个,终态集,，终态也称,可接受状态,或,结束状态,。,DFA,例3.1,DFA A=（q0,q1,q2,q3,a,b,t,q0,q0）,其中,t,定义为：,t（q0，a）=q1 t（q2，a）=q3,t（q0，b）=q3 t（q2，b）=q1,t（q1，a）=q0t（q3，a）=q2,t（q1，b）=q2 t（q3，b）=q0,状态转换表,t（q0，a）=q1 t（q2，a）=q3,t（q0，b）=q3 tq2，b）=q1,t（q1，a）=q0t（q3，a）=q2,t（q1，b）=q2 t（q3，b）=q0,字符,状态,DFA 的状态图表示,b,q2,q1,q3,q0,a,a,a,b,b,t（q0，a）=q1 t（q2，a）=q3,t（q0，b）=q3 t（q2，b）=q1,t（q1，a）=q0t（q3，a）=q2,t（q1，b）=q2 t（q3，b）=q0,a,b,定义3.2,DFA=(Q,t,q0,F,),扩充的映射,t:,Q,*,Q,定义为：,（1）,t（q，,）=q,（2）,t（q，a,）=t（t（q，a），,）,其中,qQ，a，,*,定义3.3,DFA=(Q,t,q0,F,)，,如果t（q0，,）=q,F,则符号串,可被有穷自动机,DFA,所接受。,有穷自动机,DFA,所接受的符号串集，记为,L(A).,例3,.1中的有穷自动机,A，t(q0,aabb,)=t(t(q0,a),abb,)=t(q1,abb,)=t(t(q1,a),bb)=t(q0,bb)=t(t(q0,b),b)=t(q3,b)=q0 F。,所以符号串,aabb,能被有穷自动机,A,所接受。,可接受的符号串例子,自动机的等价,定义3.4 给定两个有穷自动机,A1,和,A2，,如果,L(A1)=L(A2)，,则称自动机,A1,和,A2,等价。,例3.5,DFA A=(q0,q1,a,b,t,q0,q0),其中,t(q0,a)=q1,t(q1,b)=q0.,DFA B=(q0,q1,q2,a,b,t,q0,q2),其中,t(q0,a)=q1,t(q1,b)=q2,t(q2,a)=q1.,则,L(A)=L(B)=(,ab,),n,|n,1,所以自动机,A,B,等价。,非确定的有穷自动机,NDFA,定义3.5 一个非确定的有穷自动机是一个五元组，,NDFA=,Q，t，Q,0,，F，,其中,Q,为状态,的有穷非空,集,，,为,有穷输入,字母表,，,t,为,Q,到,Q,的子集,(多值映射),，,Q,0,Q,是初,始状,态集,，,F,Q,为终,止状,态集,。,例子,NDFA N=（S，P，Z，0，1，t，S，P，Z）,其中,t（S，0）=P,t（S，1）=S，Z,t（P，1）=Z,t（Z，0）=P,t（Z，1）=P,S,P,Z,0,0,1,1,1,1,N,状态图表示,例子3.6,NDFA=（Q，t，Q,0,，F）,其中,Q=q0,q1,q2,q3,=x,y,Q,0,=q0,F=q1.t（q0，x）=q1,q2,t（,q0，y,）=q0,t（q1，x）=q0,t（q1，y）=q1,q2,t（q2，x）=q3,t（q2，y）=q3,t（q3，x）=q1,q3,t（q3，y）=q3,q0,y,x,y,y,x,q1,NDFA,状态图表示,q3,q2,x,x,x,y,x,y,NDFA,与,DFA,的区别NDFA,有一个开始状态集合，而,DFA,只有一个开始状态；,NDFA,的映射是,Q Q,的子集，是一个多值,映射，而,DFA,是,Q Q,的一个单值,映射。,定义3.6,NDFA=(Q,t,Q,0,F,),扩充的映射,t:,Q,*,Q,定义为：,（1）,t（q，,）=q,（2）,t（q，a,）=t（q,1,，,）,t（q,2,，,）,t（,q,n,，,）,其中,qQ，a，,+,t(q,a)=q,1,q,2,q,n,定义3.3,NDFA=(Q,t,Q,0,F,)，,对于符号串,*,如果,t（q,0,，,）=q,F,则符号串,可被该非确定的有穷自动机,NDFA,所接受。,能被非确定有穷自动机,NDFA,所接受的符号串集，记为,L(A).,例3.7 证明符号串,xyx,能被例3.6中的,NDFA，,所接受。,证明：因为,t(q0,xyx,)=,t(q1,yx,),t(q2,yx,),(,t(q0,x)=q1,q2,)=,t(q1,x),t(q2,x),t(q3,x)(,t(q1,y)=q1,q2,t(q2,y)=q3,)=q0,q3 q1,q3=q0,q1,q3,q1,t(q0,xyx,)=,q0,q1,q3,q1,F,所以,xyx,能被该,NDFA,所接受。,空移环路的寻找,如果自动机的弧上允许标记,，则称此自动机为自动机，记为,NDFA,或,DFA.,q1,q2,q1,q2,q3q1,q2,q3,qn,(,a),(,b),(,c),空移环路的消除,找到空移环路之后，要消除它只要把空移环路上所有结点,q1,q2,qn,合成一个结点，并消除它们所有的,弧。如果其中的某一个结点,qi,(i=1,或2,n),是开始结点或终止结点，则将此合并后的新结点相应地设置为开始状态或终止状态。,q0,q1,q2,a,q3,q4,a,b,b,b,q0,q2,a,q3,b,b,b,a,(1),(2),例3.8,消除空移,B,q1,a,1,qn,a,n,q2,a,2,A,B,(,a),(,b),B,q1,a,1,qn,a,n,a,2,A,q2,a,1,a,2,a,n,在状态,A,与,q,i,i=1,2,n),之间添加新弧,a,i,(i=1,2,n)，,并消除状态,A,与,B,之间的,弧；,如果,B,是终止状态，则设置,A,为终止状态；,如果从开始状态经过一条路径到达,A，,设置,B,为开始状态。,重复上述过程，便可消除所有（非环路）空移。,例 3.9,(1),q0,q1,q2,d,q4,q3,d,c,d,a,b,c,q0,q1,q2,d,q4,q3,c,d,c,d,a,b,c,d,(2),b,确定化-子集法,给定一个,NDFA A=(,Q,t,Q,0,F),是一个非确定的有穷自动机，一定可以构造一个和它等价的确定有穷自动机,DFA A=(,Q,t,q,0,F)，,即,L(A)=L(A)。,构造步骤,：,(1),A,与,A,的字母表,完全相同；,(2)把,A,的每一个,状态子集,作为,A,的一个状态；,(3)对,A,的任意状态子集,r,1,r,2,r,n,，,r,i,Q(i=1,2,n)，,令,r=r,1,r,2,r,n,rQ.,A,的映射定义为,：,t(r,a)=qQ,其中,a,q=q,1,q,2,q,m,而,q,1,q,2,q,m,=t(r,1,a),t(r,2,a),t(,r,n,a);,(4)A,的,开始状态,q,0,=s,1,s,2,s,k,，,其中,s,i,Q,0,(i=1,2,k);,(5)A,的,终止状态,F,=e|e=e,1,e,2,e,p,e,1,e,2,e,p,F,.,例3.10,NDFA=（Q，t，Q,0,，F）,其中,Q=q,0,q,1,q,2,q,3,=x,y,Q,0,=q,0,F=q,1,.t（q,0,，x）=q,1,q,2,t（,q,0,，y,）=q,0,t（q,1,，x）=q,0,t（q,1,，y）=q,1,q,2,t（q,2,，x）=q,3,t（q,2,，y）=q,3,t（q,3,，x）=q,1,q,3,t（q,3,，y）=q,3,DFA=(Q,t,q,0,F).,(1),=x,y;,(2),Q=q,0,q,1,q,2,q,3,q,0,q,1,q,0,q,2,q,0,q,3,q,1,q,2,q,1,q,3,q,2,q,3q,0,q,1,q,2,q,0,q,1,q,3,q,0,q,2,q,3,q,1,q,2,q,3,q,0,q,1,q,2,q,3,(3),定义映射,t:t(q,0,x)=q,1,q,2,t(q,0,y)=q,0,t(q,1,x)=q,0,t(q,1,y)=q,1,q,2,t(q,2,x)=q,3,t(q,2,y)=q,3,t(q,3,x)=q,1,q,3,t(q,3,y)=q,3,t(q,0,q,1,x)=q,0,q,1,q,2,t(q,0,q,1,y)=q,0,q,1,q,2,.t(q,0,q,1,q,2,q,3,x)=q,0,q,1,q,2,q,3,t(q,0,q,1,q,2,q,3,y)q,0,q,1,q,2,q,3,.,(4),DFA,的开始状态,q,0,=q,0,(5),DFA,的开始状态集合,F=q,1,q,0,q,1,q,2,q,1,q,3,q,1,q,0,q,1,q,2,q,0,q,1,q,3,q,1,q,2,q,3,q,1,q,2,q,3,q,4,确定化-造表法,子集法的确定，如果状态数,n,很大，确定化后的状态数将更大2,n,-1，,并且其中很多是不可到达的状态而造表法，更加简单而有效。,步骤：,确定,DFA,的开始状态，从开始状态开始分别计算对不同输入字母的映象，如果产生新的状态，则继续计算新状态的映象，重复这个过程一直到没有新的状态出现为止。,造表法确定化输入,状态,x,y,q,0,q,0,q,1,q,2,q,1,q,0,q,0,q,1,q,2,q,1,q,0,q,3,q,2,q,1,q,2,q,3,q,3,q,0,q,3,q,2,q,1,q,2,q,3,q,3,q,0,q,3,q,2,q,1,q,2,q,3,q,3,q,0,q,1,q,3,q,4,q,1,q,2,q,3,q,3,q,0,q,1,q,3,q,4,q,0,q,1,q,2,q,3,q,5,q,0,q,1,q,2,q,3,q,5,q,0,q,1,q,2,q,3,q,5,q,0,q,1,q,2,q,3,q,5,q,0,q,1,q,2,q,3,q,5,确定化后的状态转换图,q,0,q2x,q4,x,x,y,y,x,y,q3,q1,q5,y,x,y,x,y,NDFA,的确定化,设,NDFA M=Q,t,Q,0,F,有,定义3.8,I Q，,状态子集,I,的-闭包，记为-,closure(I)，,定义如下：,(1)若,qI,则,q,-,closure(I);,(2),若,q,-,closure(I)，q,是由,q,出发经过多条弧所达到的状态，则,q,-,closure(I)。,显然，-,closure(I)Q。,定义3.9,I Q，a,映射,t(I,a)=,q|t(q,a)=q,q I,=J,Q,I,a,=,-,closure(J).,例3.12,NDFA M,的开始状态集为S，,-,closure(S)=S,将,S=q,0,作为,DFA M,的开始状态。,S,x,=,-,closure(t(S,x)=,-,closure(1)=1,2,3,S,y,=,其中1,2,3是一个新的非空子集，因此，将1,2,3=,q1,作为,M,的一个新的状态，对新子集继续求,I,x,I,y,.,一直重复上述过程一直到不再出现新状态为止。,S,1,2,3,4,5,6,7,Z,x,x,y,x,y,x,y,消除不可达状态,在自动机中，从开始状态没有一条路径能达到的状态称为,不可达状态,。不可达状态对于生成自动机的语言毫无意义，因此，应从自动机中消除。,DFA,的化简,对,DFA,化简就是使它的状态数最少，即对任意一个确定的有穷自动机,A，,要构造另一个确定的有穷自动机,A，,使,L(A)=L(A)，,且,A,的状态个数不超过,A,的状态个数。,定义3.10 如果有状态,q,1,导出的符号集和由状态,q,2,导出的符号集相等，则,DFA,的两个,状态,q,1,与,q,2,是等价的,。,定义3.11 若,DFA,的两个状态,q,1,与,q,2,不等价，则称状态,q,1,与,q,2,是,可区分的,。,DFA,化简的,基本思想,是将状态集分解成若干互不相交的子集，使每个子集的状态都是等价的，而不同子集的状态是不等价的即是可区分的。,如图，状态0和4是可区别的。,状态2和3是可区别的，因为读入,b,后分别到达2和4，而2和4不是等价的。,b,0,2,1,3,4,a,b,a,a,a,a,b,b,b,DFA M,化简步骤,(1)将状态集合分解为两个子集合，所有终止状态为一个子集，其他非终止状态为一个子集。,(2)对每个子集再进行分解，分解后的两个状态 同于一个，当且仅当对任何一个输入字母，它们的映象属于同一个子集。,(3)重复（2）一直到不能再分解为止。,例3.13,q,0,q2,x,q4,x,x,y,y,x,y,q3,q1,q5,y,x,y,x,y,先将,终止状态归为一个子集,S,1,=q,1,q,3,q,4,q,5,，,其余非终止状态归为另一个子集,S,2,=q,0,q,2因为,t(q,1,x)=q,2,S,2,t(q,3,x)=q,4,t(q,4,x)=q,5,，t(q,5,x)=q,5,S,1,，,所以将,S,1,分解为两个子集,S,1,=q,1,S,2,=,q,3,q,4,q,5,。,因为,t(q,0,x)=q,1,S,1,t(q,2,x)=q,3,S,2,所以将,S,2,分解成,q,0,q,2,q,0,q2,x,y,x,y,q1,q3,y,x,y,x,从,DFA,到程序表示,如果对,DFA,的每个状态都事先指明它所要完成的任务，再把从状态发出的弧上所标记的输入字母作看作控制条件，那么，,DFA,实际上是一个程序流程图。,q0,q1,q2,l,d,l非,l,d,标识符,DFA,char,ch,namek,name=,read(,ch,),name=name+,ch,read(,ch,),用,name,查找符,号表，若没有，,则填表，,否则返回其地址,q0,q1,q2,ch,=l,ch,=l or d,非,l,d,标识符程序流程图,从正规文法到,FA,对于正规文法,G,可以直接构造一个有穷自动机,A，,使,L（A）=L（G）。,构造步骤：,(1)正规文法,G,中终结符号集作为,A,的字母输入表；,(2)文法,G,的每个非终结符号都作为,A,的一个状态，文法的开始符号作为,A,的开始状态；,(3)在自动机,A,中增加一个新状态,z,作为自动机的中指状态；,(4)对文法,G,中形如,U,aV,(aV,T,或,a=,V V,N,),的产生式，在自动机,A,中构造形如,t(U,a)=V,的映射；,(5)对文法,G,中形如,U,a(aV,T,),的产生式，在自动机,A,中构造形如,t(U,a)=z,的映射；,例3.14,设正规文法,G,19,S：S,aS,|,aA,|,bB,A,bA,|,cC,B,aB,|,dD,C,cC,|c,D,dD,|d,由文法,G,19,构造的,FA：,S,Z,D,B,C,A,a,a,b,b,c,a,d,c,c,d,d,从,FA,到正规文法,构造步骤：,(1)自动机的每个状态标记均作为正规文法的非终结符，其中自动机开始符号的标记作为文法的开始符号。自动机的输入字母表中的所有符号作为正规文法的终结符；,(2)对于自动机的映射,t(U,a)=V（,其中,U,V,是自动机的状态标记，,a,为输入符号），构造文法的一条产生式,U,aV,U,V,非终结符，,a,终结符；,(3)对于自动机的终止状态,Z，,在正规文法中增加一条产生式：,Z,。,例3.15,构造的正规文法,G,20,S：,S,xA,|,yB,A,yA,|,yC,|,yB,B,xC,|,yC,|,C,C,A,S,y,x,y,y,B,y,x,x,y,正规表达式的定义,定义3.12 字母表,上的正规表达式和正规集递归定义如下：,(1),a,a,是,上的一个正规表达式，它所表示的正规集为,a;,(2)空串,是,上的一个正规表达式,它所表示的正规集为,;,(3)空集,是,上的一个正规表达式,它所表示的正规集为,;,(4)设,e1,e2,都是,上的正规表达式，它们表示的正规集分别为,L(e1),和,L(e2)，,则：,i)e1|e2,也是正规表达式，它所表示的正规集为,L(e1|e2)=L(e1),L(e2);,ii)e1,.,e2,也是正规表达式，它所表示的正规集为,L(e1.e2)=L(e1)L(e2);,ii)(e1),*,也是正规表达式，它所表示的正规集为,L(e1),*,)=(L(e1),*,.,正规表达式的性质,定义3.13 设,e1e2,是,上的正规表达式，若,L(e1)=L(e2)，,则,e1,与,e2,等价，记为,e1=e2.,如,a|(,ba,),*,=(,ba,),*,|a.,设,e1,e2,是,上的正规表达式，则,e1|e2=e2|e1;,(e1e2)e3=e1(e2e3),(e1|e2)|e3=e1|(e2|e3);,e1(e2|e3)=e1e2|e1e3,(e1|e2)e3=e1e3|e2e3;,e1=e1,=,e1,正规,式,和,有穷自动机,的等价性,1.,对于,上的,N,D,FA M，可以构造一个,上的正规式,e,使得,L(,e,)=L(M)。,2,.对于,上的一个正规式,e,，可以构造一个,上的N,D,FA M，使得L,(,M)=L(e)。,正规表达式到,NDFA,的转换,步骤,:(1)先构造一个广义的,NDFA,转换图，只有,S，Z,两个状态，,S,是开始状态，,Z,是终止状态，弧上是正规表达式,e;(2),按照下面替换规则，对,e,进行分解，直到转换图中所有弧上都是,的单个符号或,为止。,A,C,B,e,1,e,2,A,B,e,1,e,2,A,B,e,1,e,2,A,B,e,1,|,e,2,A,C,B,e,1,A,B,e,1,*,(1),(2),(3),替换规则,例3.17,设,=,x,y,上的正规表达式,e=,xy,*,(,xy,|,yx,)x,*,，,构造一个,NDFA M，,使L(M)=L(e).,S,Z,e=,xy,*,(,xy,|,yx,)x,*,S,Z,1,3,6,x,y,*,(,xy,|,yx,),x,*,S,Z,2,3,6,x,xy,x,1,y,7,yx,S,Z,2,3,6,x,y,x,1,y,7,x,4,5,y,x,NDFA,到正规表达式的转换,步骤,:(1)在,NDFA,中新设置一个唯一的开始状态,S,和唯一的终止状态,Z；,(2),从开始状态,S,到原来的开始状态连接,弧，再从原来的终止状态到,Z,状态也连接弧；,(3)按照替换规则进行替换，直到状态图中只剩下,S,和,Z，,在,S，Z,弧上的表达式就是所求的结果。,从正规文法到正规表达式,转换规则1)产生式,U,V,V,VV,N,V,T,*,转换成正规表达式,U=;,(2)产生式,U,U|,转换成,U=,*,;,(3)产生式,U,|,转换成,U=|;,例3.19 正规文法,G,21,S:,S,dA,|,eB,A,aA,|b,B,bB,|c,根据转换规则：,A,aA,|b,转换成,A=a,*,b,(,规则2),B,bB,|c,转换成,B=b,*,c(,规则2,),则有产生式,S,da,*,b|,eb,*,c,所以,S=,da,*,b|,eb,*,c（,规则3）,DFA,在计算机中的表示,DFA=(Q,t,q,0,F),中映射,Q,Q,的表示方法。,1、矩阵表示法,状态集,Q,的所有状态排序:,q,0,q,1,q,2,.,q,n,，,字母表 上的所有字母排序:,a,0,a,1,a,2,.,a,m,。,设,M,是一个二维数组，若,t(,q,i,a,j,)=,q,k,则令,Mi,j=k，,其中,i,k=0,1,2,n;j=0,1,2,m。,2、表结构,在这个表结构中，每个状态对应一个表，表中包括该状态的状态名、从该状态发出的弧数、每条弧上的标记（输入字母）以及弧所达到的状态所在表的首地址。,小结,有穷自动机形式定义,NFA,DFA,的转换,正规文法与有穷自动机,正规表达式与,FA,DFA,在计算机中的表示,