计算理论课件第二章.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章,有限自动机和正规文法,2.1,确定的有限自动机,(,DFA),(Determinate Finite Automaton),有限自动机是研究自动系统的一种数学模型，它出现,于本世纪四十年代。,1943年由,McCulloch,与,Pitts,建立了模拟神经网络的自动机,1956年由,Moore,建立了描述计算机的时序机的概念。,以后自动机的理论日趋发展，并且与计算机的信息处理,密切结合，它不仅用于研究计算机的结构，还用于研究,形式语言语言的识别。,在这里主要是从识别语言这方面来研究自动机。,一.有限自动机(,FA),的结构,有限自动机由三部分构成：,1.输入带,输入带可以任意长，带上,有若干单元，每个单元内,有输入符号。输入带上存,放的是被有限自动机识别,的符号串。如图所示，,输入带上的符号串为：,a,1,a,2,a,3,a,n,。,2.,读头,读头是将输入带上的符号读到有限控制器中，每次读,一个单元的符号。,有 限 控 制 器,a,1,a,2,a,3,a,n,输入带,读头,3.有限控制器,有限控制器是有限自动机的核心。,有限自动机有多个状态，有一个开始状态，还,有若干个终止状态。,自动机每读带上一个符号,状态可能发生变化，,然后读头右移一个单元。,自动机如何从开始状态出发，识别完带上的整,个符号串后，要进入某个终止状态，这个过程就,是由有限控制器控制的。,二.确定的有限自动机(,DFA),的形式描述,定义,：确定的有限自动机,M,写成有序五元组，记,作,M=(K,q,0,F),其中，,K,有限自动机的状态的有限集合。,输入带上的有穷字母表。,状态转移函数,是,KK,的映射。,例如，,(q,a)=p(,其中,q,pK,a),表示在,q,状态下，读,a,后，状态改为,p,然后，将读头右移,一个单元。,q,0,开始状态,q,0,K,F,终止状态集合，,F,K,三.确定的有限自动机的表示方法,【例2-1.1】,给定确定的有限自动机,M=(K,q,0,F),K=q,0,q,1,q,2,q,3,=0,1,F=q,0,:(q,0,0)=q,2,(q,0,1)=q,1,(q,1,0)=q,3,(q,1,1)=q,0,(q,2,0)=q,0,(q,2,1)=q,3,(q,3,0)=q,1,(q,3,1)=q,2,状态转移函数,也可以,用函数表表示,，如上表所示。,0 1,q,0,q,2,q,1,q,1,q,3,q,0,q,2,q,0,q,3,q,3,q,1,q,2,a,q,(q,a)=q,(,c),q,q,F,(,d),q,0,开始状态,q,0,(,a),q,p,(q,a)=p,(,b),a,有限自动机还可以,用图表示,。方法如下：,四状态转移函数,定义的扩充,原,：,KK,的映射。,1,1,0,0,q,0,q,1,q,2,q,3,1,1,0,0,0 1,q,0,q,2,q,1,q,1,q,3,q,0,q,2,q,0,q,3,q,3,q,1,q,2,(,q,)=q,M,的状态转移图:,为描述有限自动机,M,接收的语言，将,函数扩充成 ：,：K,*,K,的映射。对于任何,x,*,，,如果,一般地表示：,(,q,x)=p,表示在状态,q,下，读,符号串,x,后，到状态,p。,(q,xa,)=(q,x),a),其中,x,*,，a,例如上例中,(,q,0,010)=(q,0,01),0)=(q,0,0),1),0),(q,2,1),0)=(q,3,0)=q,1,。,(q,0,),0),1),0)=(q,0,0),1),0),但此时的,一定理解成 。,(,q,0,010)=q,1,也可以写成,(q,0,010)=q,1,。,造成混淆，所以,起见，符号,与 可以不作区分地使用，这样做也不会,可见在确定的有限自动机中，是由,定义的,为了简单,五确定的有限自动机,M,接收的语言,T(M),给定确定的有限自动机,M=(K,q,0,F)，M,接收的,语言,T(M),为：,T(M)=w|w,*,且,(q,0,w)=p,其中,pF,例2-1.1中，,T(M)=?,1,1,0,0,q,0,q,1,q,2,q,3,1,1,0,0,T(M)=w|w0,1,*,且,w,中有偶数个0或者偶数个1。,作业题,1,设计一个有限自动机(,FA)M，,使得,T(M),中的每个句子,w,同时满足下面三个条件：,1),wa,b,*,；,2),|w|,是3的整数倍；,3),w,以,a,开头，以,b,结尾。,2,设计二个,FA M,1,和,M,2,，,分别满足,T(M,1,)=0,2i,i,是自然数,T(M,2,)=0,2i+1,i=0,1,2,3,4,2,.,2,不确定的有限自动机（,NFA,）,(Non-deterministic Finite Automaton),DFA,是在每个状态下，读一个符号后的下一个状态是,唯一确定的，下面讨论的有限自动机是在某个状态下，,读一个符号后的下一个状态可能不是唯一确定的，这就,是不确定的有限自动机。,一.不确定的有限自动机（,NFA）,的形式定义,定义,：不确定的有限自动机,M，,用一个有序五元组表示：,M=(K,q,0,F),其中，,K、,、,q,0,、,F,的含义同,DFA,。,状态转移函数,是,K2,K,的映射。,例.,(q,a)=p,s(,其中,qK,p,s,2,K,a),【例2-2.1】,.给定,NFA M，M=(K,q,0,F),其中，,K=q,0,q,1,q,2,q,3,q,4,=0,1 F=q,2,q,4,：K2,K,为：,0 1,q,0,q,0,q,3,q,0,q,1,q,1,q,2,q,2,q,2,q,2,q,3,q,4,q,4,q,4,q,4,q,0,q,1,q,2,q,3,q,4,0,1,0,1,0,1,0,0,1,1,图,2-2.1,NFA M,状态转移图,二.状态转移函数,定义的扩充,原来,：K2,K,，,下面对它进行,两次扩充,。与确,定的有穷自动机相类似，,扩充以后的状态转移函数仍,然用,。因为这样做,在计算时也不会引起错误。,1.,将,扩充成：,：K,*,2,K,，,定义为：,x,*,(q,x)=p,1,p,2,p,n,（p,1,p,2,p,n,2,K,）,表示在状态,q,下,读,符号串,x,后,可以达到状态,p,i,(1in)。,一般地表示：,(q,)=q qK,(q,xa,),其中,qK,x,*,，a,(q,0,01)=(q,0,1)(q,3,1)=q,0,q,1,=q,0,q,1,例2-2.1,中,(q,0,0)=q,0,q,3,则,为了计算,(q,xa,),方便，,2.,将,的定义再一次扩充成：,：,2,K,2,K,，,对于任何,Pp,1,p,2,p,n,2,K,，a,(2)(q,xa,)=(q,x),a),即,(P,a),等于,P,中每个状态分别读,a,后状态集合的并集。,的定义经过扩充之后，计算,(q,xa,),的式子可写成：,(q,xa,)=(q,x),a)。,于是对于任何,x,*,a,(1),(q,)=q qK,(P,a)=(p,1,p,2,p,n,a)=,三.,NFA M,所接收的语言,T(M),给定,NFA M=(K,q,0,F),M,所接收的语言,T(M),为：,T(M)=w|w,*,且,(q,0,w)F,例2-2.1中，,T(M)=?,T(M)=w|w0,1,*,且,w,中或者有两个相邻的0或者有两,个相邻的1,q,0,q,1,q,2,q,3,q,4,0,1,0,1,0,1,0,0,1,1,图,2-2.1,NFA M,状态转移图,四,NFA,转换成,DFA,任何一个,NFA,都可以等价地转换成,DFA。,定理2-2.1,如果语言,L,可由一个,NFA M,所接收，则必存,在一个,DFA M，,使得,T(M)=L。,证明,：令,NFA M=(K,q,0,F)，,且,T(M)=L。,构造,DFA M=(K,q,0,F),其中,K,2,K,，K,中的元素是由,K,的子集,q,1,q,2,q,i,构成，但,是要把子集,q,1,q,2,q,i,作为的一个状态看待，因此把此,子集写成,q,1,q,2,q,i,。,q,0,=,q,0,F,=q,1,q,2,q,i,|q,1,q,2,q,i,K,且,q,1,q,2,q,i,F,：KK，,对,q,1,q,2,q,i,K,a，,有,(,q,1,q,2,q,i,a)=p,1,p,2,p,j,当且仅当,(q,1,q,2,q,i,a)=p,1,p,2,p,j,这说明：计算,时，完全取决于,NFA,中,（,注,：为了更好地理解如何根据,NFA M,构造,DFA M,，,可,以先看例子，然后再看下面的证明，这样更容易理解证,明的过程。）,例.,将例2-2.1中的,NFA M,等价变换成,DFA M。,按照上述定,理给定的方法。令,M,(K,q,0,F)，,其中，,K、F:,因为,K,2,K,，,在,求,K,时,，不需要将2,K,中的所有元素都列,入,K,只需要列入,从开始状态,q,0,可以达到的状态即可,为,此可以先求,，然后得到,K,和,F。,例2-2.1,：,NFA M=(K,q,0,F),其中，,K=q,0,q,1,q,2,q,3,q,4,=0,1 F=q,2,q,4,构造,DFA M=(K,q,0,F),q,0,=,q,0,:,q,1,q,2,q,i,K,a,有,(,p,1,p,2,p,j,a)=q,1,q,2,q,n,当且仅当,(p,1,p,2,p,j,a)=q,1,q,2,q,n,从,q,0,开始，计算各个可达状态的转移函数。,例如,要计算,(,q,0,q,3,0),首先计算,(q,0,q,3,0)。,(q,0,q,3,0)=(q,0,0)(q,3,0)=q,0,q,3,q,4,=q,0,q,3,q,4,于是,(,q,0,q,3,0)=q,0,q,3,q,4,其余的依此类推。最后得下表,0 1,q,0,q,0,q,3,q,0,q,1,q,1,q,2,q,2,q,2,q,2,q,3,q,4,q,4,q,4,q,4,:,K=q,0,q,0,q,3,q,0,q,1,q,0,q,3,q,4,q,0,q,1,q,2,q,0,q,2,q,3,q,0,q,1,q,4,q,0,q,2,q,3,q,4,q,0,q,1,q,2,q,4,F=q,0,q,3,q,4,q,0,q,1,q,2,q,0,q,2,q,3,q,0,q,1,q,4,q,0,q,2,q,3,q,4,q,0,q,1,q,2,q,4,0 1,q,0,q,0,q,3,q,0,q,1,q,0,q,3,q,0,q,3,q,4,q,0,q,1,q,0,q,1,q,0,q,3,q,0,q,1,q,2,q,0,q,3,q,4,q,0,q,3,q,4,q,0,q,1,q,4,q,0,q,1,q,2,q,0,q,2,q,3,q,0,q,1,q,2,q,0,q,2,q,3,q,0,q,2,q,3,q,4,q,0,q,1,q,2,q,0,q,1,q,4,q,0,q,3,q,4,q,0,q,1,q,2,q,4,q,0,q,2,q,3,q,4,q,0,q,2,q,3,q,4,q,0,q,1,q,2,q,4,q,0,q,1,q,2,q,4,q,0,q,2,q,3,q,4,q,0,q,1,q,2,q,4,：,0 1,q,0,q,0,q,3,q,0,q,1,q,1,q,2,q,2,q,2,q,2,q,3,q,4,q,4,q,4,q,4,:,M,的图：,q,0,q,0,q,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,q,0,q,1,q,2,q,0,q,3,q,4,q,0,q,2,q,3,q,0,q,1,q,4,q,0,q,2,q,3,q,4,q,0,q,1,q,2,q,4,图,2-2.2,M,的状态转移图,q,0,q,3,证明,：,T(M)=T(M),1.,先用归纳法证明(对输入符号串|,x|,归纳)下面命题成立：,对于任何,x,*,，,(q,0,x)=q,1,q,2,q,n,当且仅当,(q,0,x)=q,1,q,2,q,n,(1),当|,x|=0，,即,x=,时，,(,q,0,)=q,0,=q,0,当且仅当,(q,0,)=q,0,，,命题成立。,(2),假设|,x|k,时，命题成立。即,(,q,0,x)=p,1,p,2,p,j,当且仅当,(q,0,x)=p,1,p,2,p,j,(3),当|,xa,|=k+1,时，,a,有,(,q,0,xa,)=(q,0,x),a),(q,0,xa,)=(q,0,x),a),因为|,x|=k,由假设(2)得,(,q,0,x)=p,1,p,2,p,j,当且仅当,(q,0,x)=p,1,p,2,p,j,。,故,(,q,0,xa,)=(p,1,p,2,p,j,a),当且仅当,(q,0,xa,)=(p,1,p,2,p,j,a)，,所以命题成立。,2.,再证明,T(M)=T(M),对于任何,x,*,如果,xT(M)，,则,(,q,0,x)F，,令,(,q,0,x)=p,1,p,2,p,j,，,即,p,1,p,2,p,j,F。,因命题,(,q,0,x)=p,1,p,2,p,j,当且仅当,(q,0,x)=p,1,p,2,p,j,成立。,由,F,定义得,p,1,p,2,p,j,F,当且仅当,p,1,p,2,p,j,F，,即,(q,0,x)F。,于是,xT(M)。,所以,T(M)=T(M)。,定理证明完毕。,从此定理看出:与,DFA,相比，,NFA,并没有扩大它所接收语言的范围。,作业题,给定,NFA M,1,=(p,q,r,s,0,1,p,s)，,如下表所示。构造一个,DFA M,2,，,使得,T(M,1,)=T(M,2,)。,0 1,p p,q p,q r r,r s ,s s s,2.3,具有,转移的,NFA,（,简记成,-,NFA,）,前边讨论的,NFA,中的输入符号只是中的符号，在理,论上和实际应用中还有另一种,NFA，,就是输入符号中除,了中的符号以外，还允许有,，,这就是具有,转移的,NFA(-NFA)。,【例2-3.1】,具有,转移的,NFA M(-NFA M)，,如图2-3.1所示。从图中看出，,图中有的有向边上标有,。,q,0,q,1,q,2,0,1,2,图2-3.1,-NFA M,图,一,-NFA,的形式定义,-NFA M=(K,q,0,F)，,其中,K,q,0,F,的含义同前边,NFA,:K()2,K,例2-3.1中的,-NFA M,的,如表2-3.1所示。,0 1 2,q,0,q,0,q,1,q,1,q,1,q,2,q,2,q,2,表2-3.1,-NFA M,状态转移表,q,0,q,1,q,2,0,1,2,图2-3.1,-NFA M,图,为了讨论,-NFA,接收的语言需要对,的定义进行扩充。,二,的定义扩充,先扩充成 ：,K,*,2,K,定义为,对于,qK,w,*,值得注意:,在,DFA,和,NFA,中,对于扩充后的 与,可以不加,(,q,0,)=q,0,径(即在0的前后可能有若干个,)，,而不是输入符号0。,(q,0,0)=q,0,q,1,q,2,(q,0,0)=q,0,因为这里的0指的是0路,(,q,0,)=q,0,q,1,q,2,(,q,0,)=q,0,，,因为这里的,指的是,路径，而不是边上标的,。,而在,-NFA,中，在例2-3.1中,(q,0,0)=q,0,q,3,=(q,0,0),区别的使用，因为它们的计算结果相同。但是在这里,就,必须加以区别,因为它们的计算结果不同了。请看下例:,在,NFA,中，在例2-2.1中，,(q,w)=P=p|,从,q,出发，沿着标有,w,的,路径,达到状态,p,q,0,q,1,q,2,0,1,2,图2-3.1,-NFA M,图,为了写出 (,q,w),的计算公式，下面再定义两个概念。,三,-CLOSURE(q),qK,-CLOSURE(q)=p|,从,q,出发,沿着,路径达到状态,p,上例中，,-CLOSURE(q,0,)=q,0,q,1,q,2,-CLOSURE(q,1,)=q,1,q,2,-CLOSURE(q,2,)=q,2,四.,-CLOSURE(P),（,其中,P,是状态的集合）,P,是状态的集合，则,-CLOSURE(P)=-CLOSURE(q),上例中，,-CLOSURE(q,0,q,1,),=-CLOSURE(q,0,),-CLOSURE(q,1,),=,q,0,q,1,q,2,q,1,q,2,=q,0,q,1,q,2,五.对,及的定义的再扩充,将,的定义扩充成,：,2,K,2,K,，,注意,(,q,wa,)(q,w),a)，,因路径,wa,是指,w,*,a,*,(q,wa,)=-CLOSURE(q,w),a),公式(2),：对于,qK,w,*,a,公式(1),：对于,qK,(q,)=-CLOSURE(q),六的计算公式,对,R2,K,w,*,(R,w)=(r,w),再扩充成 ：,2,K,*,2,K,(,(q,w),a),前边加,-CLOSURE。,所以要在,对,R2,K,，,a，(R,a)=(r,a),q,0,q,1,q,2,0,1,2,图2-3.1,-NFA M,图,例如,在上例中,计算 (,q,0,01),按照递归地定义公式(2),要,先计算：,(,q,0,)=q,0,q,1,q,2,再计算：,(,q,0,0)=-CLOSURE(q,0,),0),=-CLOSURE(q,0,q,1,q,2,0),=-CLOSURE(q,0,0)(q,1,0)(q,2,0),=-CLOSURE(q,0,),=-CLOSURE(q,0,)=q,0,q,1,q,2,最后计算,(,q,0,01)=-CLOSURE(q,0,0),1),=-CLOSURE(q,0,q,1,q,2,1),=-CLOSURE(q,0,1)(q,1,1)(q,2,1),=-CLOSURE(q,1,),=-CLOSURE(q,1,),=q,1,q,2,七.,-NFA M,接收的语言,T(M),给定一个,-NFA M=(K,q,0,F)，,它接收的,语言,T(M),为：,T(M)=w|w,*,且 (,q,0,w)F,上例中,T(M)=0,i,1,j,2,k,|i,j,k0,八.,-NFA,等价地转换为,NFA,一个,-NFA M,可以等价地转换为没有,转移,的,NFA。,下面介绍定理。,定理2-3.1,如果语言,L,由一个有,转移的,NFA M,所接收，则,L,可被一个不具有,转移的,NFA M,所接收。,证明：,令一个,-NFA M=(K,q,0,F)，,它接收的语言,T(M),为,L。,构造一个不具有,转移的,NFA M,M=(K,q,0,F)，,其中,：对任何,qK,任何,a,(q,a)=(q,a)。,下面证明,T(M)=T(M)。,先用归纳法(任何,x,+,，,对|,x|,归纳)证明下面命题成立：,对于任何,x,+,有,(,q,0,x)=(q,0,x),(,当讨论,x=,时,不,用此结论),(1),当|,x|=1,时，设,x=a，a，,根据的定义，有,(,q,0,a)=(q,0,a)，,命题成立。,(2),假设|,x|k,时,命题成立。即,(,q,0,x)=(q,0,x)。,(3).,当|,xa,|=k+1,时，令输入符号串,xa,(x,+,|x|=k,a),根据归纳假设有,(,q,0,x)=(q,0,x)。,因为,(,q,0,xa,)=(q,0,x),a)，,=(q,0,x),a)(,根据的扩充定义),=(,q,0,x),a)(,根据假设（2）),=(,q,0,xa,),综上所述，上述命题成立。,先证,T(M),T(M),任取,xT(M)，,若,x,，,则,-CLOSURE(q,0,)F，,由,F,的构成得,F=Fq,0,，,而,(,q,0,)q,0,所以,(,q,0,)F，,所以,T(M)。,若,x,，,则 (,q,0,x)F，,由已经证明的命题得,(,q,0,x)F，,由,F,定义得,F,F，,所以,(,q,0,x)F，,所以,xT(M)。,所以,T(M),T(M),。,再证,T(M),T(M),任取,xT(M),下面分两种情况,1),如果,x=，,因,M,是无,的,NFA，,必有,(,q,0,)=q,0,F,，,所以,q,0,F，,再分两种情况讨论:,(1),若,q,0,F，,又有,q,0,-CLOSURE(q,0,),所以,-CLOSURE(q,0,)F,而,即 (,q,0,)F，,所以,T(M)。,(2),若,q,0,F,，,而,q,0,F，,这说明,F,=F,q,0,，,即说明,-CLOSURE(q,0,)F，,即 (,q,0,),F,，,所以,T(M)。,-CLOSURE(q,0,)(q,0,)，,2),如果,x，,分两种情况讨论,(1),.如果,F=F，,因为,(,q,0,x)F，,由上述命题知,(,q,0,x)=(q,0,x)，,所以必有 (,q,0,x)F，,所以,xT(M)。,(2),如果,F=Fq,0,，,又已知,(,q,0,x)F，,这又有两种可能：,(,a),若,q,0,(q,0,x)，,则有,(,q,0,x)F(q,0,x)(Fq,0,),(q,0,x)F)(q,0,x)q,0,),(q,0,x)F),(q,0,x)F ,即 (,q,0,x)F，,所以,xT(M)。,(,b),若,q,0,(q,0,x)，,所以,q,0,(q,0,x)，,说明在,M,中从,q,0,出发沿着,x,路径可以回,(,b),若,q,0,(q,0,x)，,因为 (,q,0,x)=(q,0,x)，,到,q,0,，,进而也可以达到,-CLOSURE(q,0,),中的各个状态，,因而有,-CLOSURE(q,0,),(q,0,x)，,又,F=Fq,0,，,由,F,定义知,-CLOSURE(q,0,)F，,于是,(,q,0,x)F，,所以,(,q,0,x)F，,所以,xT(M)。,综上所述，有,T(M),T(M),。,最后得,T(M)=T(M),。,例,.下面将例2-3.1中的,-NFA M,等价变换成,NFA M。,令,M=(K,q,0,F)，,其中,K=q,0,q,1,q,2,=0,1,2,F=q,0,q,2,的计算如下：,图,2-3.2,NFA M,图,q,0,q,2,q,1,0,1,2,2,1,0,0,1,1,2,0 1 2,q,0,q,0,q,1,q,2,q,1,q,2,q,2,q,1,q,1,q,2,q,2,q,2,q,2,:,(q,0,0)=(q,0,0)=q,0,q,1,q,2,(q,0,1)=(q,0,1),=-CLOSURE(q,0,),1),=-CLOSURE(q,0,q,1,q,2,1),=-CLOSURE(q,0,1)(q,1,1)(q,2,1),=-CLOSURE(q,1,),=-CLOSURE(q,1,)=q,1,q,2,其它的依此类推。,最后得,的表2-3.2。,M,的图如图2-3.2所示。,作业题,将下面的,-NFA M,等价变换成,NFA M。,a,b,c,d,e,f,1,0,1,0,2.4,正规表达式及其与有限自动机之间的等价性,有限自动机所接受的语言，很容易用字母表上的符号,串以及符号串上的一些运算符号构成的表达式来表示，,即用正规表达式来表示。,一.正规表达式定义,设,是有限字母表，,上的正规表达式及其所代表的符,号串集合递归定义如下：,1.,是个正规表达式，它代表空集,。,2.,是个正规表达式，它代表集合,。,3.,任何,a，,是个正规表达式，它代表集合,a。,4.,如果,r、s,分别是代表集合,R、S,的正规表达式,则(,r+s)、,(,rs,)、(r,*,),分别是代表集合(,RS)、(RS)、(R,*,),的正规表,达式。,r+s,称作,r,与,s,的加运算；,rs,称作,r,与,s,的连接运算；,r,*,称作,r,的,*,闭包运算。,设,r,是个正规表达式，则,r,所代表的集合记作,L(r)。,例如，,L()=,L(a)=a,二正规表达式运算的优先级,为了书写简单，看起来也简单明了，我们规定了正规,表达式运算的优先权，于是正规表达式的最外层的括号,以及表达式里的一些括号可以省略。,运算的优先权:,从高到低依次是：,*,、连接、。,因此，(0+(0(1,*,)可以简记为 001,*,。,例如,设,0,1，,则,1.01 表示集合,L(01)01=01,2.0+1,表示集合,L(0+1)=L(0)L(1)=01=0,1,3.(0+1),*,表示集合,L(0+1),*,)=0,1,*,=,0,1,00,01,10,11,000,001,4.0,*,表示集合,L(0),*,)=0,*,=,0,00,000,0000,5.1(0+1),*,表示集合,L(1(0+1),*,)=10,1,*,=1,0,1,00,01,10,11,000,001,=1,10,11,100,101,110,111,1000,1001,三两个正规表达式相等,设,、,是,上的正规表达式，如果,L()=L(),则称,与,相等，记作,。,四.重要的等式,（正规表达式的运算性质）,、,是,上的正规表达式，则,1.,(+,满足交换律),2.,(+,满足幂等律),3.,=(,是运算的幺元),4.,(,)+(+)(+,满足可结合性),5.,(+)(,连接对满足分配律),证明,：,L(+)L()L()=L()(L()L()=L()L()L()L()=L()L()=L(),6.,(+),7.,=(,是连接运算的幺元),8.,(,是连接运算的零元),证明,：,L()L()L()L()=L(),所以,，,类似可证,9.,()=()(,连接运算满足可结合性),10.,*,证明,：对任何集合,A,*,A,0,AA,2,A,3,A,4,其中,A,0,=,所以,L(,*,),*,=,0,2,=,0,=L(),11.,+,*,=,*,12.,(,*,),*,=,*,在离散数学中,二元关系,R,有，,R,*,=,rt,(R)=,tr,(R),(,R,*,),*,=R,*,13.,*,=,*,=,+,在离散数学中，二元关系,R,有，(,R,R,*,)=R,*,R=R,+,14.,(+),*,=,*,因,L(+),*,)=,*,=,0,1,2,=,2,2,3,=,2,3,=,*,=L(,*,),15.,+,+,=,*,16.,(),*,+,*,=,*,因为,*,*,五.正规表达式与有限自动机之间的等价性,下面证明有限自动机所接受的语言正好是一个正规表,达式所表示的语言。反之亦然,即任意给定正规表达式,r,都可以确定一个,FA M，,使得,T(M)=L(r)。,正规表达式与有限自动机之间的等价关系，可以用下面,图2-4.1表示。,正规表达式,NFA,NFA,DFA,图2-4.1 有限自动机与正规表达式之间的等价转换关系图,定理2-4.1,设,r,是,上的一个正规表达式，则存在一个具,有,转移的,NFA M,使得,T(M)=L(r)。,证明,：用对,r,中含有运算的个数归纳证明。,1.,如果,r,中有0个运算，则有三种可能:,r=,r=,r=a a,则有下面三个自动机分别接受它们。,q,0,q,0,q,1,a,q,0,q,1,r=,r=,r=a,2.,假设,r,中运算个数少于,k,个时，结论成立。,3.,当,r,中有,k,个运算时，因正规表达式中只有三种运算，所,以分三种情况讨论：,(1),如果,r=r,1,+r,2,则,r,1,和,r,2,中运算个数少于,k,个，由假设得，,存在,NFA M,1,和,M,2,，,使得,T(M,1,)=L(r,1,)T(M,2,)=L(r,2,),不妨设,M,1,(K,1,1,1,q,1,f,1,)M,2,(K,2,2,2,q,2,f,2,),设,K,1,K,2,=,下面构造,NFA M,M(K,1,K,2,q,0,f,0,1,2,q,0,f,0,)，,其中,q,0,f,0,K,1,K,2,使得,T(M)=T(M,1,)T(M,2,)=L(r,1,)L(r,2,)=L(r,1,+r,2,),于是,M,的结构如下图所示：,M,1,M,2,q,1,q,2,q,0,f,1,f,2,f,0,M,的状态转移函数,为：,(q,0,)=q,1,q,2,M,可以进入,M,1,和,M,2,的开始状态。,对任何,qK,1,任何,a,1,有,(q,a)=,1,(q,a),M,可以模拟,M,1,的动作。,对任何,qK,2,任何,a,2,有,(q,a)=,2,(q,a),M,可以模拟,M,2,的动作。,(f,1,)=(f,2,)=f,0,很容易证明,T(M)=T(M,1,)T(M,2,)，,这里从略。,(2),.如果,r=r,1,r,2,则,r,1,和,r,2,中运算个数少于,k,个,由假设得，,存在,NFA M,1,和,M,2,使得,T(M,1,)=L(r,1,)T(M,2,)=L(r,2,),M,1,和,M,2,如前所述。,下面构造,NFA M(K,1,K,2,1,2,q,1,f,2,)，,使,得,T(M)=T(M,1,)T(M,2,)=L(r,1,)L(r,2,)=L(r,1,r,2,),于是,M,的结构如,下图所示：,M,1,q,1,f,1,M,2,q,2,f,2,M,的状态转移函数,为：,对任何,qK,1,任何,a,1,有,(q,a)=,1,(q,a)M,可以模拟,M,1,的动作。,(f,1,)=q,2,对任何,qK,2,任何,a,2,有,(q,a)=,2,(q,a)M,可以模拟,M,2,的动作。,很容易证明,T(M)=T(M,1,)T(M,2,)，,这里从略。,(3),.如果,r=r,1,*,则,r,1,中运算个数少于,k,个，由假设得，存,在,NFA M,1,使得,T(M,1,)=L(r,1,),M,1,如前所述。,下面构造,NFA M(K,1,q,0,f,0,1,q,0,f,0,)，,使得,T(M)=(T(M,1,),*,=(L(r,1,),*,=L(r,1,*,),于是,M,的结构如下,图所示：,q,0,M,1,q,1,f,1,f,0,M,的状态转移函数,为：,(q,0,)=q,1,f,0,对任何,qK,1,任何,a,1,有,(q,a)=,1,(q,a)M,可以模拟,M,1,的动作。,(f,1,)=q,1,f,0,下面证明,T(M)=(T(M,1,),*,：,任何,wT(M),如果,w=,因为,(T(M,1,),0,，,而(,T(M,1,),0,(T(M,1,),*,，,所以,(T(M,1,),*,所以,w(T(M,1,),*,。,如果,w,，,根据,M,的结构可以看出，一定可以将,w,写,成,w=w,1,w,2,w,3,w,k,形式，其中,k1，,每个,w,i,(1ik),都使得在,M,1,中从,q,1,出发沿着标有,w,i,的路径达到,f,1,识别,完,w,k,后最后经过,转移达到状态,f,0,，M,接受输入,w。,显然上述每个,w,i,(1ik),都属于,T(M,1,),所以,w,1,w,2,w,3,w,k,(T(M,1,),k,(T(M,1,),k,(T(M,1,),*,，,所以,w,1,w,2,w,3,w,k,(T(M,1,),*,，,所以,w(T(M,1,),*,。,于是得,T(M),(T(M,1,),*,类似可以证明(,T(M,1,),*,T(M)。,最后得,T(M)=(T(M,1,),*,。,【例2-4.1】,给定正规表达式,r=01,*,1，,构造一个,-NFA,M,使得,T(M)=L(r)。,解,.,1,.先将,r,分解，找出,r,中所含基本符号0、1、1，,然后分别构造出接受这些基本符号的有限自动机，如下,图所示,。,q,5,q,6,1,q,1,q,2,0,q,3,q,4,1,q,3,q,4,1,q,7,q,8,q,1,q,2,0,q,3,q,4,1,q,7,q,8,2,.按照运算的优先权，从高到低进行“组装”。,先组装接受1,*,的有限自动机，如下：,再组装接受01,*,的有限自动机，如下,：,最后组装接受01,*,+1的有限自动机,M，,如下：,f,q,0,q,3,q,4,1,q,7,q,8,q,1,q,2,0,q,5,q,6,1,此,NFA M,就是接受正规表达式,r,的有限自动机。,上面我们讨论了由给定的正规表达式,r,求接受,r,的有限自,动机，当然可以将,NFA M,等价转换成,NFA,进而还可,以转换成,DFA。,下面的问题就是，给定,DFA M，,如何求出,T(M),的正规,表达式的问题。,定理2-4.2,如果语言,L,可由一个,DFA,M,接受，则,L,可用,一个正规表达式表示。,证明,：设,L,由一个,DFA M(K,q,1,F),接受，不妨,设,K=q,1,q,2,q,n,。,求,T(M),所对应的正规表达式,r，,即使,得,L(r)=T(M)。,因为,T(M),是由,上这样字符串,w,构成的集合，这些字符,串,w,都使得,M,从开始状态,q,1,出发沿着标有,w,的路径，途中经,过,K,中某些状态，而最后达到,F,中的某个状态。为此我们,定义符号串集合 。,：是由,上这样字符串,x,构成的集合，这些,x,都使得,M,从状态,q,i,出发沿着标有,x,的路径，最后到达,q,j,而途中经,过所有状态的下标都不大于,k。,就表示使得,M,从状态,q,i,出发，最后到达,q,j,的所有符号,串构成的集合。于是,问题是如何计算 ，下面就给出它的递归计算公式,：,其中 表示从状态,q,i,出发，不经过任何状态直接到达,q,j,的所有符号串构成的集合。因此当,ij,时，就是,M,的有向图上从,q,i,到,q,j,的有向边上标的符号构成的集合。当,i=j,时，除了有向环上标的符号外，还包括,。,由两部分组成：,一部分是 ，中的符号串,x,可使得,M,从状态,q,i,出发,沿着标有,x,的路径，最后到达,q,j,而途中经过所有状态的,下标都不大于,k-1,而不经过状态,q,k,。,q,j,q,k,q,i,x,1k,x,kk,x,kj,另一部分是 ，其中的符号串,x,可使得,M,从状,态,q,i,出发沿着标有,x,的路径，最后到达,q,j,而途中必经过,状态,q,k,。,这里,x,可以由三个子串的连接组成，例如，,x,ik,x,kk,x,kj,则,x=,x,ik,(,x,kk,),*,x,kj,，,识别,x,的路,线如下图所示：,显然 可以用正规表达式 表示，它的计算公式如下：,下面通过一个例子说明如何应用上面公式求,DFA M,的,T(M),的正规表达式,r.,【例2-4.1】,给定,DFA M,如,图2-4.2所示。求,T(M),的正规,表达式,r.,解,1.,k=0,q,2,0,1,q,1,q,3,1,0,1,0,图2-4.2,2.,K=1:,3.K=2,4.K=3,5.T(M),的正规表达式,r,为,：,作业题,1,化简正规表达式,a(+,aa,),*,(+a)b+b+(,ab,*,+b),*,2,构造一个,FA M，,使得,T(M),的正规表达式为01+(0+1),*,1),*,。,3,给定,FA M,如下图所示，求它所接收的语言,T(M),的正规表达式。,q,2,q,1,0,0,1,1,2-5 有限自动机的简化,对于给定的一个有限自动机,M，,有时可以在保证接受语,言,T(M),不变的情况下，进行简化，即求一个含有更少状,态的有限自动机,M，,使得,T(M,)=T(M)。,例如下面有限自动机,M,就可以简化成,M,，,它们接受的语,言都是1,*,如图2-5.1所示。,图,2-5.1,q,2,1,q,3,1,1,q,1,1,1,M:,q,1,1,M:,给定一个,DFA M,如何进行简化。主要的思路是先定义,自动机状态集合,K,上的一个等价关系,，然后用,将,K,进,行划分得到商集,K/,，,再构造状态更少的有限自动机。,一.定义,K,上等价关系,给定,DFA,M=(K,q,0,F)，,p,qK,p,q,对,x,*,有,(p