(精品)编译原理第二章_(4)

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,复习,一,.,确定有限自动机,确定有限自动机,M,为一个五元组,:,M=(,S,s,0,f,Z)，,其中：,S,：,是一个有穷状态集，它的每个元素称为一个状态；,：,是一个有穷字母表，它的每个元素称为一个输入,字符；,s,0,S,：,是唯一的一个初始状态,(,开始状态,),；,F,：,是状态转换函数,:S,S,，且单值函数；,Z,S,：是终止状态集（可接受状态集、结束状态集）。,二、非确定有限自动机,NFA,一个非确定有限自动机(,NFA)M,是一个五元组：,M=(,S,S,0,f,Z),，其中：,S,：是一个有限集合，它的每个元素称为一个状态；,：是一个有穷字母表，它的每个元素称为一个输入字符；,S,0,:S,0,S,是非空初始状态集；,f,：是状态转换函数，它是一个从,S,(,),到,S,的子集的映射，即,S,(,),2,s,；,Z:Z S ,是终止状态集。,三.,DFA,的两种表示方式,状态转换图：用有向图表示自动机,DFA M=(S,U,V,Q,a,b,f,S,Q),其中,f,定义为：,f(S,a)=U f(V,a)=U,f(S,b)=V f(V,b)=Q,f(U,a)=Q f(Q,a)=Q,f(U,b)=V f(Q,b)=Q,状态转换图,U,S,V,Q,a,a,b,a,b,a,b,b,DFA,接受的字符串,对于,*,中的任何字符串,t,若存在一条从初始结点到某一终止结点的路径,，,且这条路上所有弧上的标记符连接成的字符串等于,t,则称,t,可为,DFA M,所,接受（识别）,。,若,DFA M,的初始状态同时又是终止状态，则空字符串可为,DFA M,所,接受（识别）,。,DFA M,所能接受的字符串的全体记为,L(M).,状态转换矩阵：用二维数组描述,DFA,DFA M=(S,U,V,Q,a,b,f,S,Q),其中,f,定义为：,f(S,a)=U f(V,a)=U,f(S,b)=V f(V,b)=Q,f(U,a)=Q f(Q,a)=Q,f(U,b)=V f(Q,1)=Q,输入字符,状态,a,b,S,+,U,V,U,Q,V,V,U,Q,Q,*,Q,Q,五、,DFA,的实现,1,状态转换矩阵的形式：,1.当前状态,State,置为初始状态；,2.读一个字符,CurrentChar,；,3.如果,CurrentChar,Eof,并且,T(State,CurrentChar,),error,，,则当前状态转为新的状态,:,State,=,T(State,Current,),，,读下一字符,CurrentChar,；,重复第3步工作。,4.如果当前字符为,Eof,并且当前状态属于终止状态，则接受当前字符串，程序结束；否则报错。,b,DFA,的实现2,状态转换图的形式：,每个状态对应一个带标号的,switch,语句,转向边对应,goto,语句,1.,非终止状态对应的,switch,语句,i,j,k,a,L,i,:switch(,CurrentChar,),case a ：,goto,L,j,;,case b :,goto,L,k,;,default :Error();,2.,终止状态对应的,switch,语句,i,j,k,L,i,:,seitch,(,CurrentChar,),case a ：,goto,L,j,;,case b :,goto,L,k,;,case,Eof,:Accept;,default :Error();,a,b,例,:,a,a,b,1,0,2,a,b,a,L,0,:switch(,CurrentChar,),case a ：,goto,L,1,;,case a ：,goto,L,0,;,case b :,goto,L,0,;,default :Error();,2.3.3 NFA,到,DFA,的转换,定义,2.26,有限自动机的等价,对于给定的有限自动机,M,1,和,M,2,，如果有,L(M,1,)=L(M,2,),则称有限自动机,M,1,和,M,2,等价。,定理,2.5,对于每一个非确定,有限,自动机,M,，存在一个确定,有限,自动机,M,，使得,L(M)=L(M),。,NFA,确定化,由,NFA,构造出与其等价的,DFA,称为,NFA,确定化。,两个重要函数：,状态集,I,的闭包,设,I,是,NFA M,状态集的子集，定义,I,的闭包,_CLOSURE(I),为：,若,q I,则,q _CLOSURE(I),。,若,q I,那么从,q,出发经任意条,弧而能到达的任何状态,q,都属于,_CLOSURE(I),。,例,:,_CLOSURE(1)=,1,，,2,1,5,2,4,6,3,7,8,9,6,7,9,a,a,b,b,b,a,状态集,I,的,a,转换,若,I=S,1,S,m,是,NFA,的,状态集的,一个,子集（,状态子集），,a,则定义,:,I,a,=,_CLOSURE(J),其中,:,J=,f(S,1,a),f(S,2,a),f(S,m,a,),例,:1,，,2,a,=,_CLOSURE(J),J=f(1,a)f(2,a)=4,5,1,，,2,a,=,_CLOSURE(4,5)=4,5,7,6,2,1,5,2,4,6,3,7,8,9,6,7,9,a,a,b,b,b,a,NFA A,到,DFA A,的转换过程,(,确定化,):,1.,令,I,0,=,_CLOSURE(S,0,),作为,DFA,的初始状态，其中,S,0,为,NFA,初始状态集。,2.,若,DFA,中的每个状态都经过本步骤处理过.则转步骤,3,；否则任选一个未经本步骤处理的,DFA,状态,S,i,，,对每一个,a,进行下述处理：,计算,S,j,=S,ia,若,S,j,，则令,f(,S,i,a)=,S,j,，,若,S,j,不为当前,DFA,的状态，则将其作为,DFA,的一个状态。,转步骤,2,。,3.,若,S=S,1,S,n,是,A,的一个状态,且存在一个,S,i,是,A,的终止状态，则令,S,为,A,的终止状态。,例题,例,1:,将如下的,NFA,转化为,DFA,。,1,5,2,4,6,3,7,8,9,6,7,9,a,a,b,b,b,a,转化的结果如下：,1,3,6,9,4,5,a,b,b,a,a,6,2,转化过程：,_CLOSURE(S,0,),=,_CLOSURE(1),=1,2,1,5,2,4,6,3,7,8,6,7,9,a,a,b,b,b,a,(1,2),a,=,_CLOSURE(4,5),=4,5,7,6,2,(1,2),b,=,_CLOSURE(3),=3,8,4,5,7,6,2,a,=,_CLOSURE(,),=,4,5,7,6,2,b,=,_CLOSURE(,9,3,),=9,3,8,3.8,a,=,_CLOSURE(,9,),=9,3.8,b,=,_CLOSURE(,),=,3.9,8,a,=,_CLOSURE(,9,),=9,3.9,8,b,=,_CLOSURE(,),=,9,b,=,_CLOSURE(,),=,9,a,=,_CLOSURE(,),=,算法,输入字,状态,a,b,1,2,4,5,7,6,2,3,8,3,8,4,5,7,6,2,9,3,8,9,3,8,9,9,9,*,*,*,输入字,状态,a,b,2,1,4,3,1,2,4,5,7,6,2,3,8,3,8,4,5,7,6,2,9,3,8,9,3,8,9,9,9,*,*,*,5,2,3,4,5,5,1,3,2,4,5,b,a,b,a,a,例,2:,将如下的,NFA,转化为,DFA,b,b,b,a,a,0,1,2,4,3,5,6,7,8,9,10,I,a,b,x,5,1,-,closure(x,),=x,5,1,5,1,3,5,1,4,5,1,3,2,6,y,5,1,4,5,1,3,5,1,4,2,6,y,5,1,3,2,6,y,5,1,4,6,y,5,1,3,6,y,5,1,4,2,6,y,5,1,3,6,y,5,1,4,2,6,y,5,1,3,2,6,y,5,1,4,6,y,5,1,4,2,6,y,5,1,4,5,1,3,2,6,y,5,1,3,5,1,4,6,y,5,1,3,6,y,1,y,3,4,b,a,x,5,2,6,b,b,a,a,a,b,例,2:,将如下的,NFA,转化为,DFA,x,5,1,a,=5,3,1,x,5,1,b,=5,4,1,5,1,3,a,=5,3,2,1,6,y,5,1,3,b,=5,4,1,5,1,4,a,=5,3,1,5,1,4,b,=5,4,2,1,6,y,5,1,3,2,6,y,a,=5,3,2,6,1,y,5,1,3,2,6,y,b,=5,4,6,1,y,a,b,x,5,1,1,5,1,3,2,5,1,4,3,5,1,3,2,5,1,3,2,6,y,4,*,5,1,4,3,5,1,4,3,5,1,3,2,5,1,4,2,6,y,5,*,5,1,3,2,6,y,4,*,5,1,3,2,6,y,4,5,1,4,6,y,6,*,5,1,4,2,6,y,5,*,5,1,3,6,y,7,*,5,1,4,2,6,y,5,*,5,1,4,6,y,6,*,5,1,3,6,y,7,*,5,1,4,2,6,y,5,*,5,1,3,6,y,7,*,5,1,3,2,6,y,4,*,5,1,4,6,y,6,*,包含原终,态的状态,作为新的,终态,1,a,2,3,b,4,a,b,5,b,a,7,a,a,b,a,6,b,b,b,2.3.4 DFA,的化简,DFA,的化简的必要性,1,2,3,4,5,6,7,a,b,c,c,b,d,7,a,b,c,b,d,1,2,3,4,5,6,c,7,a,b,c,b,d,1,2,3,4,5,6,c,7,a,b,c,b,d,1,2,3,4,5,6,c,7,a,b,c,b,d,1,2,3,4,5,6,c,7,b,5,6,c,a,b,c,d,1,2,3,4,a,b,c,d,1,2,3,4,等价状态,定义,1,设,DFA M,的两个状态,q,1,和,q,2,如果对任意输入的符号串,x,，从,q,1,和,q,2,出发，总是同时到达接受状态或拒绝状态中，则称,q,1,和,q,2,是等价的。如果,q,1,和,q,2,不等价，则称,q,1,和,q,2,是可区分的。,定义,1,对,DFA,中的两个状态,q,1,和,q,2,，如果将它们看作是初始状态，所接受的符号串相同，则定义,q,1,和,q,2,是等价的。,注意,:,DFA,的,终止状态和非终止状态不是等价的。,无关状态,从有限自动机的初始状态开始，任何输入序列都不能到达的那些状态称为无关状态。,最小的,DFA(,化简了的,DFA),如果,DFA M,没有无关状态，也没有彼此等价的状态，则称,DFA M,是最小的（或规约的）。,状态分离法,状态分离法,状态分离法的目标,:,SS=SS,1,SS,2,SS,n,其中,:,SS,i,SS,j,=,(i j,时,),，并且每个,SS,i,中的所有状态均等价。,状态集,SS,i,对,a(a,),是不可区分的,:,若,SS,i,中元素对输入符,a,都转到相同的状态集中,.,状态集,SS,i,对,a(a,),是可区分的,:,若,SS,i,中元素对输入符,a,转到不同的状态集中,.,状态集,SS,i,对,a(a,),进行划分,:,若,SS,i,中元素对输入符,a,转到不同的状态集中,则分别将转到相同集合中的状态组成一个新的状态集,.,1,2,3,4,5,6,7,a,b,c,c,b,d,例：,1,，,8,2,，,5,3,，,6,4,，,7,2,，,5,对,b,是不可区分的；,3,，,6,对,c,是不可区分的；,1,，,8,对,a,是可区分的；,1,，,8,对,a,进行划分：,1,8,8,b,a,状态分离法算法,STEP,1,求初始划分,:,SS=,非终止状态集终止状态集。,STEP,2,若,SS,中的每个子集对每一个,a(a,),都是不可区分