正则语言的性质

单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,*,,,1,形式语言与自动机,第,5,章 正则语言的性质,2,主要内容,正则语言,(RL),的性质,,泵引理及其应用,,并、乘积、闭包、补、交,,正则代换、同态、逆同态的封闭性,,从正则语言固有特征寻求表示的一致性,,Myhill-Nerode,定理,,FA,的极小化,,正则语言的几个判定问题,,空否、有穷否、两个,DFA,等价否、成员关系,3,5.1,正则语言的泵引理,DFA,在处理一个足够长的句子的过程中，必定会重复地经过某一个状态换句话说，在,DFA,的状态转移图中，必定存在一条含有回路的从启动状态到某个终止状态的路由于是回路，所以,DFA,可以根据实际需要沿着这个回路循环运行，相当于这个回路中弧上的标记构成的非空子串可以重复任意多次q,1,,q,k,,q,j,,,,,4,泵引理,5,泵引理,M,= (,Q,, ∑, δ,,q,0,,,F,),,|,Q,|=,N,,,z,=,a,1,a,2,…,a,m,,,,m,≥,N,,,δ(,q,0,,,a,1,a,2,…,a,h,) =,q,h,,,,状态序列,q,0,,,q,1,, … ,,q,N,,中，至少有两个状态是相同：,q,k,=,q,j,,δ(,q,0,,,a,1,a,2,…,a,k,) =,q,k,,δ(,q,k,,,,a,k,+1,…,a,j,) =,q,j,,=,q,k,,δ(,q,j,,,,a,j,+1,…,a,m,) =,q,m,,,因此，可设,z,=,,u,v,w,，其中,,,u,=,,a,1,a,2,…,a,k,，,v,=,a,k,+1,…,a,j,，,w,=,a,j,+1,…,a,m,,6,泵引理,对于任意的整数,i,≥0,,,δ(,q,k,, (,a,k,+1,…,a,j,),i,),,=δ(,q,k,,, (,a,k,+1,…,a,j,),i,-1,),,…,,=δ(,q,k,,,a,k,+1,…,a,j,) =,q,k,,,故,δ(,q,0,,,a,1,a,2,…,a,k,,(,a,k,+1,…,a,j,),i,,a,j+1,…,a,m,) =,q,m,,也就是说，,,a,1,a,2,…,a,k,,(,a,k,+1,…,a,j,),i,,a,j,+1,…,a,m,∈,L,(,M,),,即,u,v,i,w,∈,L,,。

7,泵引理,(pumping lemma),,设,L,为一个 正则语言 ，则存在仅依赖于,L,的正整数,N,，,,对于,,z,∈,L,，如果,|,z,|≥,N,，则存在,u,,,v,,,w,，满足,,(1),z,=,uvw,；,,(2),|,uv,| ≤,N,；,,(3),|,v,| ≥ 1,；,,(4),对于任意的整数,i,≥0,，,u,v,i,w,∈,L,；,,(5),N,不大于接受,L,的最小,DFA,M,的状态数我们总能够在离,z,,的开始处不太远的地方找到一个非空的,,串,v,，然后可以把它看作一个“,泵,”，重复,v,,任意多次，,,或者去掉它，而所得到的结果串仍然属于,L,8,例,5-1,,证明,{ 0,n,1,n,|,n,≥1 },不是,RL,证明：假设,L,={ 0,n,1,n,|,n,≥1},是,RL,不妨设,N,是泵引理所指的仅依赖于,L,的正整数,，取,,,z,= 0,N,1,N,,，则,z,∈,L,按照泵引理所述，存在,u,,,v,,,w,，使得,z,=,uvw,由于,,|,uv,| ≤,N,，,|,v,| ≥ 1,，所以,v,,只能由,0,组成，,,可设,v,=0,k,，,k,≥1,,,此时有，,u,= 0,N,-,k,-,j,,,,w,=0,j,1,N,,,,从而有，,uv,i,w,= 0,N,-,k,-,j,(0,k,),i,0,j,1,N,,= 0,N,+(i-1),k,1,N,,,,当,i,=2,时,，有：,,,uv,2,w,=0,N,+(2-1),k,1,N,= 0,N,+,k,1,N,,,注意到,k,≥1,，所以，,N,+,k,>,N,。

这就是说，,0,N,+,k,1,N,,L,这与泵引理矛盾所以，,L,不是,RL,9,例,5-2,,证明,{ 0,n,|,n,为素数,},不是,RL,证明：,假设,L,={ 0,n,|,n,为素数,},是,RL,取,z,=0,N,+,p,,∈,L,,，,N,+,p,是素数不妨设,v,=0,k,，,k,≥1,,从而有,,,uv,i,w,=0,N,+,p,-,k,-,j,(0,k,),i,0,j,,=0,N,+,p,+(,i,-1),k,,当,i,=,N,+,p,+1,时,，,,,N,+,p,+(,i,-1),k,=,N,+,p,+(,N,+,p,+1-1),k,,=,N,+,p,+(,N,+,p,),k,,= (,N,+,p,)(1+,k,),,注意到,k,≥1,，所以,,,N,+,p,+(,N,+,p,+1-1),k,=(,N,+,p,)(1+,k,),,不是素数故当,i,=,N,+,p,+1,时，,,uv,N,+,p,+1,w,=0,(,N,+,p,)(1+,k,),,,L,,这与泵引理矛盾所以，,L,不是,RL,10,例,5-3,证明,{ 0,n,1,m,2,n,+,m,|,m,,,n,≥1 },不是,RL,。

证明：假设,L,={ 0,n,1,m,2,n,+,m,|,m,,,n,≥1 },是,RL,取,z,=0,N,1,N,2,2,N,,,设,v,=0,k,,k,≥1,,,从而有,uv,i,w,,= 0,N,-,k,-,j,(0,k,),i,0,j,1,N,2,2,N,,,= 0,N,+(,i,-1),k,1,N,2,2,N,,,uv,0,w,= 0,N,+(0-1),k,1,N,2,2,N,,,= 0,N,-,k,1,N,2,2,N,,,注意到,k,≥1,，,,N,-,k,+,N,=2,N,-,k,<2,N,,0,N,-,k,1,N,2,2,N,,,L,,这个结论与泵引理矛盾所以，,L,不是,RL,11,泵引理的说明,用来证明一个语言不是,RL,,不能用泵引理去证明一个语言是,RL,1),由于泵引理给出的是,RL,的必要条件，所以，在用它证明一个语言不是,RL,时，我们,使用反证法,2),泵引理说的是对,RL,都成立的条件，而我们是要用它证明给定语言不是,RL,，这就是说，相应语言的“仅仅依赖于,L,的正整数,N”,实际上是不存在的所以，我们一定是无法给出一个具体的数的因此，人们往往就,用符号,N,来表示这个“假定存在”、而实际并不存在的数,。

3),由于泵引理指出，如果,L,是,RL,，则对任意的,z,∈,L,，,只要,|,z,|≥N,，一定会存在,u,,,v,,,w,，使,uv,i,w,∈,L,对所有的,i,成立,因此，我们在选择,z,,时，就需要注意到论证时的简洁和方便12,泵引理的说明,(4),当一个特意被选来用作“发现矛盾”的,z,,确定以后，就必须依照,|,uv,| ≤,N,和,|,v,|≥1,的要求，说明,v,不存在,(,对“存在,u,,,v,,,w,”,的否定,),5),与选,z,,时类似，在寻找,i,,时，我们也,仅需要找到一个表明矛盾的“具体”值,就可以了,(,对“所有,i,”,的否定,),6),一般地，在证明一个语言不是,RL,的时候，我们并不使用泵引理的第,(5),条7),事实上，引理所要求的,|,uv,| ≤,N,并不是必须的这个限制为我们简化相应的证明提供了良好支撑,——,扩充了的泵引理 8),如果希望证明一个语言是,RL,，最直接的办法是给出该语言的正则文法描述，或者是,FA, RE,描述,也可以直接使用一些已有的结果和,RL,的性质13,5.2,正则语言的封闭性,封闭性,(closure property),,,如果任意的、属于同一语言类的语言在,某一特定运算下所得的结果仍然是该类语言,，则称该语言类对此运算是封闭的,,有效封闭性,(valid closure property),,,给定一个语言类的若干个语言的描述，,如果存在一个算法,，它可以,构造出这些语言在给定运算下所获得的运算结果的相应形式的语言描述,，则称此语言类对相应的运算是有效封闭的。

本节讨论,RL,的封闭性,,RL,在哪些运算下是封闭的？,,14,正则语言的封闭性,,定理,5-1,RL,在并、乘积、闭包运算下是封闭的根据,RE,的定义，立即可以得到此定理定理,5-2,RL,在补运算下是封闭的要点：,原来接受的不接受，不接受的接受证明：,,,M,=(,Q,,,∑,, δ,,q,0,,,F,),L,(,M,)=,L,，,,取,DFA,M,',= (,Q,,,∑,, δ,,q,0,,,Q,-,F,),,,显然，对于任意的,x,∈,∑,*,，,,,δ(,q,0,,,x,)=,f,∈,F,,,δ(,q,0,,,x,)=,f,,Q,-,F,,,,即,x,∈,L,(,M,),,,x,,L,(,M,',),，,,,L,(,M,',)=,∑,*,-,L,(,M,),所以，,RL,在补运算下是封闭的定理得到证明15,RL,的交,,定理,5-3,RL,在交运算下封闭,利用,M,1,∩,M,2,= ~(~,M,1,∪~,M,2,),即可证明构造,M,1,= (,Q,1,, ∑, δ,1,,,q,1,,,,F,1,),和,M,2,= (,Q,2,, ∑, δ,2,,,q,2,,,F,2,),的交,DFA,。

M,= (,Q,1,×,Q,2,, ∑, δ,,, (,q,1,,,,q,2,),,,,F,1,×,F,2,),,δ((,p,,,q,),,a,) = (δ,1,(,p,,,a,), δ,2,(,q,,,a,) ),16,RL,的交,1,q,p,0,0,1,S,0,s,r,1,0,1,S,pr,1,1,S,0,qs,qr,1,0,1,ps,0,0,17,正则语言的封闭性,定理：,如果,L,,和,M,,是正则语言，则,L,-,M,,也是正则语言证明：利用,L,-,M,=,L,∩ ~,M,定理：,如果,L,,是正则语言，则,L,R,,= {,x,|,x,R,,∈,L,},也是正则语言构造接受,L,R,,的有穷状态自动机：,,(1),把,M,的状态转移图中的所有有向边的指向逆转2),令,M,的初始状态为新的有穷自动机的唯一的接受状态3),增加一个状态,p,0,为新的有穷自动机的初始状态，同时从该状态出发到,M,,的所有接受状态都建立一个,ε,转移18,问题,对字母表,∑,上的,RL,L,，令,DFA,M,= (,Q,,∑,δ,,q,,,,F,),识别,L,对于任意,(,q,,,a,)∈Q×,∑,，设,δ(,q,,,a,)=,p,，,f,(,a,),是,Δ,上的一个,RL,，假定,DFA,M,a,= (,Q,a,, Δ,δ,a,,,q,0,a,,,,F,a,),识别,f,(,a,),。

下面构造,FA,M,RS,，主框架是,M,，而它的“分支子模块”是,M,a,M,,在状态,q,,读入字符,a,时进入状态,p,，,,让,M,RS,在状态,q,作空移动到,M,a,,的开始状态,q,0,a,，,,并在,M,a,,中处理,f,(,a,),，之后它一定处在,M,a,,的某个终止状态从,M,a,的每一个终止状态到,M,,的状态,p,,引一条标记为,ε,的弧,，,,使,M,RS,回到状态,p,如此下去，直到最后到达,M,,的终止状态可见，,RL,在这种运算下也是封闭的称这种运算为,正则代换,19,正则代换,,(regular substitution),设,∑,,Δ,是,两个字母表，映射,称为是从,∑,到,Δ,的,代换,如果对于,,a,∈,∑,，,f,(,a,),是,Δ,上的,RL,,，则称,f,,为,正则代换,将,f,,的定义域扩展到∑,*,上：,,(1),f,(ε)={ε},；,,(2),f,(,xa,)=,f,(,x,),f,(,a,),将,f,,的定义域扩展到,对于,,L,,∑,*,,20,例,5-4,,设∑,={ 0, 1 },，,Δ={,a,,,b,},，,f,(0)=,a,，,f,(1)=,b,*,，则,,f,(010),,=,f,(0),f,(1),f,(0),,=,ab,*,a,,f,({11,00}),,=,f,(11)∪,f,(00),,=,f,(1),f,(1)∪,f,(0),f,(0),,=,b,*,b,*,+,aa,,=,b,*,+,aa,f,(,L,(0,*,(0+1)1,*,)),,=,L,(,a,*,(,a,+,b,*,)(,b,*,),*,),,=,L,(,a,*,(,a,+,b,*,),b,*,),,=,L,(,a,*,ab,*,+,a,*,b,*,b,*,),,=,L,(,a,*,b,*,),21,正则代换,,是正则代换,,,则,,(1),f,(Φ)=Φ,；,,(2),f,(ε)=ε,；,,(3),对于,,a,∈∑,，,f,(,a,),是,Δ,上的,RE,；,,(4),如果,r,,,s,,是∑上的,RE,，则,,,f,(,r,+,s,) =,f,(,r,)+,f,(,s,),,,f,(,rs,) =,f,(,r,),f,(,s,),,,f,(,r,*,) =,f,(,r,),*,,是,Δ,上的,RE,。

设∑,, Δ,是两个字母表，映射,22,定理,5-4,定理,5-4,设,L,,是∑上的一个,RL,，,,,是正则代换，则,f,(,L,),也是,RL,证明思路：使用,RE,进行定理证明因为,L,,是,RL,，则存在正则表达式,r,，使得,L,(,r,)=,L,对,r,,中,运算符的个数,,n,,施以归纳，证明,f,(,r,),是表示,f,(,L,),的,RE,即证明：,f,(,L,(,r,) ) =,L,(,f,(,r,) ),,当,n,=0,时，结论成立当,n,≤,k,时定理成立，即当,r,,中运算符的个数不大于,k,,时：,,f,(,L,(,r,) ) =,L,(,f,(,r,) ),当,n,=,k,+1,时， 分,3,种情况：,,(1),r,=,r,1,+,r,2,(2),r,=,r,1,r,2,(3),r,=,r,1,*,23,定理,5-4,(1),r,=,r,1,+,r,2,f,(,L,)=,f,(,L,(,r,) ),,=,f,(,L,(,r,1,+r,2,) ),,=,f,(,L,(,r,1,)∪,L,(,r,2,) ) RE,的定义,,,=,f,(,L,(,r,1,))∪,f,(,L,(,r,2,) ),正则代换的定义,,,=,L,(,f,(,r,1,))∪,L,(,f,(,r,2,) ),归纳假设,,,=,L,(,f,(,r,1,)+,f,(,r,2,)) RE,的定义,,,=,L,(,f,(,r,1,+,r,2,) ) RE,的正则代换的定义,,,=,L,(,f,(,r,) ),24,定理,5-4,(2),r,=,r,1,r,2,。

f,(,L,)=,f,(,L,(,r,) ),,=,f,(,L,(,r,1,r,2,)),,=,f,(,L,(,r,1,),L,(,r,2,)) RE,的定义,,,=,f,(,L,(,r,1,)),f,(,L,(,r,2,)),正则代换的定义,,,=,L,(,f,(,r,1,)),L,(,f,(,r,2,)),归纳假设,,,=,L,(,f,(,r,1,),f,(,r,2,) ) RE,的定义,,,=,L,(,f,(,r,1,r,2,) ) RE,的正则代换的定义,,,=,L,(,f,(,r,) ),25,定理,5-4,(3),r,=,r,1,*,f,(,L,)=,f,(,L,(,r,) ),,=,f,(,L,(,r,1,*,) ),,=,f,(,L,(,r,1,),*,) RE,的定义,,,= (,f,(,L,(,r,1,)) ),*,,正则代换的定义,,,= (,L,(,f,(,r,1,)) ),*,,归纳假设,,,=,L,(,f,(,r,1,),*,) RE,的定义,,,=,L,(,f,(,r,1,*,)) RE,的正则代换的定义,,,=,L,(,f,(,r,) ),26,例,5-5,设∑,={ 0, 1, 2 },，,Δ={,a,,,b,},，正则代换,f,定义为：,,,,f,(0)=,ab,；,f,(1)=,b,*,a,*,；,f,(2)=,a,*,(,a,+,b,),,则：,,(1),f,(00)=,abab,；,,(2),f,(010)=,abb,*,a,*,ab,=,ab,+,a,+,b,；,,(3),f,((0+1+2),*,)=(,ab,+,b,*,a,*,+,a,*,(,a,+,b,)),*,,,=(,b,*,a,*,+,a,*,(,a,+,b,)),*,=(,a,+,b,),*,；,,(4),f,(0(0+1+2),*,)=,ab,(,ab,+,b,*,a,*,+,a,*,(,a,+,b,)),*,,,=,ab,(,a,+,b,),*,；,,(5),f,(012)=,abb,*,a,*,a,*,(,a,+,b,)=,ab,+,a,*,(,a,+,b,),；,,(6),f,((0+1),*,) = (,ab,+,b,*,a,*,),*,,,= (,ab,+,b,+,a,+,b,*,a,*,),*,=(,a,+,b,),*,。

27,同态映射,(homomorphism),设 ∑,, Δ,是两个字母表，,f,为映射，如果对于,,x,,,y,∈∑,*,，,,f,(,xy,) =,f,(,x,),f,(,y,),,则称,f,为从 ∑ 到,Δ,*,的,同态映射,28,同态映射,对于,,L,,∑,*,，,L,的同态像,对于,,w,,Δ,*,，,w,的同态原像是一个集合,对于,,L,,Δ,*,，,L,的同态原像是一个集合,,,,,L,f,(L),,,,,f,,-1,(L),L,29,例,5-6,设∑,={ 0, 1 },，,Δ={,a,,,b,},，同态映射,f,,定义为,,,f,(0)=,aa,,,f,(1)=,aba,,(1),f,(01)=,aaaba,；,,(2),f,((01),*,)= (,aaaba,),*,；,,(3),f,,-1,(,aab,)=,Φ,；,,(4),f,,-1,(,aa,)={0},；,,(5),f,,-1,({,aaa,,,aba,,,abaaaaa,,,abaaaaaa,}),,={ 1, 100 },；,,(6),f,,-1,((,ab,+,ba,),*,a,)={1},；,,(7),f,(,f,,-1,((,ab,+,ba,),*,a,))=,f,({1})={,aba,},。

令,L,=(,ab,+,ba,),*,a,，上述,(7),表明，,f,(,f,,-1,(,L,) ) ≠,L,可以证明,f,(,f,,-1,(,L,) ),,L,,,30,RL,的同态像是,RL,推论,5-1,,RL,的同态像是,RL,注意到,同态映射是正则代换的特例,，可以直接得到此结论该定理表明，,RL,在同态映射下是封闭的,定理,5-5,,RL,的同态原像是,RL,,31,RL,的同态原像是,RL,定理,5-5,,RL,的同态原像是,RL,,证明思路：使用,DFA,作为描述工具接受,RL,的同态原像的,FA,的构造思想让新构造出的,FA,M',用一个移动去模拟,M,,处理,f,(,a,),所用的一系列移动,对于∑中的任意字符,a,，如果,M,,从状态,q,开始处理,f,(,a,),，并且当它处理完,f,(,a,),时到达状态,p,，则让,M',在状态,q,读入,a,时，将状态变成,p,M,',具有与,M,,相同的状态,，并且，在,M,',对应的状态转移图中，从状态,q,到状态,p,有一条标记为,a,的弧当且仅当在,M,的状态转移图中，有一条从状态,q,,到状态,p,,的标记为,f,(,a,),的路。

32,RL,的同态原像是,RL,接受,RL,的同态原像的,FA,的形式描述设,DFA,M,=(Q,Δ,δ,,q,0,, F ),，,L,(,M,)=,L,，,,取,DFA,M,',=(Q,∑,δ,',,,q,0,, F ),,δ,',(,q,,,a,)= δ(,q,,,f,(,a,) ),,为了证明,L,(,M,',)=,f,-1,(,L,(,M,)),,只需证明，对于任意,x,∈,∑,*,，,,,δ,',(,q,0,,,x,) ∈F,,,δ(,q,0,,,f,(,x,)),∈F,,为此，先证明,δ,',(,q,0,,,x,) =,δ(,q,0,,,f,(,x,)),,33,RL,的同态原像是,RL,证明,δ,',(,q,0,,,x,)=,δ(,q,0,,,f,(,x,)),,施归纳于,|,x,|,当,|,x,| =0,时，结论显然成立设当,|,x,|=,k,是结论成立，往证当,|,x,|=,k,+1,时结论成立不妨设,x,=,ya,，其中,|,y,|=,k,,,δ,',(,q,0,,,x,)=,δ,',(,q,0,,,ya,),,=,δ,',(,δ,',(,q,0,,,y,),,a,),,=,δ,',(,δ,(,q,0,,,f,(,y,)),,a,),归纳假设,,,=,δ,(,δ,(,q,0,,,f,(,y,)),,f,(,a,) ),δ,',的定义,,,=,δ,(,q,0,,,f,(,y,),f,(,a,) ),δ,的意义,,,=,δ,(,q,0,,,f,(,ya,)),同态映射性质,,,=,δ,(,q,0,,,f,(,x,)),34,RL,的同态原像是,RL,这表明，结论对,|,x,|=,k,+1,成立。

由归纳法原理，结论对,,x,∈∑,*,成立现在证明：,,x,∈∑,*,，,δ,',(,q,0,,,x,)∈F,,δ(,q,0,,,f,(,x,)) ∈F,由于对,,x,∈∑,*,，,δ,',(,q,0,,,x,)=δ(,q,0,,,f,(,x,) ),，,,所以，,,,δ,',(,q,0,,,x,)∈F,,δ(,q,0,,,f,(,x,))∈F,故,,,L,(,M,',)=,f,-1,(,L,(,M,) ),,定理得证35,商,(quotient),设,L,1,,,L,2,,∑,*,，,L,1,除以,L,2,的商定义为：,,L,1,/,L,2,={,x,|,,y,∈,L,2,使得,xy,∈,L,1,},,,计算语言的商主要是考虑语言,句子的后缀,只有当,L,1,的句子的后缀在,L,2,,中时，其相应的前缀才属于,L,1,/,L,2,36,商,(quotient),考虑,{0, 1},上的如下语言：,,,(1),L,1,=(0+1),*,，,L,2,=0(0+1),*,， 则,L,1,/,L,2,=,L,1,,(2),L,1,=01,，,L,2,=01,， 则,L,1,/,L,2,={ε},,,L,1,=(01),*,，,L,2,=(01),*,， 则,L,1,/,L,2,=,L,1,,(3),L,1,=0,*,011,*,，,L,2,=00,， 则,L,1,/,L,2,=Φ,,(4),L,1,=(0+1),*,0,，,L,2,=(0+1),*,1,， 则,L,1,/,L,2,=Φ,,(5),L,1,=00,*,1,*,1,，,L,2,=,00,*,1,*,1,， 则,L,1,/,L,2,=,0,*,,(6),L,1,=00,*,1,*,1,，,L,2,=,0,*,1,*,1,， 则,L,1,/,L,2,=,0,*,1,*,,注意：,(,L,1,/,L,2,),L,2,=,L,1,,和,L,1,/,L,2,,,L,1,,不一定成立。

37,商,(quotient),注意以下有意思的情况：,,取,L,1,={ 000 },，并分别除以,,,L,2,={,ε,},,L,3,={,ε,,0},,L,4,={,ε,,0,00 },,L,5,={,ε,,0, 00, 000 },,,L,1,/,L,2,={ 000 }=,L,1,,,L,1,/,L,3,={ 000, 00 },,,L,1,/,L,4,={ 000, 00, 0 },,,L,1,/,L,5,={ 000, 00, 0,,ε,},,注意：,在充当“被除数”的集合不变的情况下，充当“除数”的集合越“大”，所得的“商”可能越大38,L,1,/,L,2,的封闭性,定理,5-6,,L,1,,,L,2,,∑,*,，如果,L,1,是,RL,，则,L,1,/,L,2,也是,RL,,证明：设,L,1,,,∑,*,，,L,1,是,RL,，,,则存在,DFA,M,1,=(,Q,,∑,δ,,q,0,,,F,1,),，使得,L,(,M,1,,)=,L,1,,,构造,DFA,M,2,,= (,Q,,∑,δ,,q,0,,,F,2,,),,,其中,F,2,,={,q,|,,y,∈,L,2,,δ(,q,,,y,)∈,F,1,},,,显然,L,(,M,2,,)=,L,1,/,L,2,。

定理得证39,5.3 Myhill-Nerode,定理与,DFA,的极小化,对给定,RL,L,，,DFA,M,接受,L,，,M,不同，由,M,,确定的∑,*,上的等价类也可能不同如果,M,,是最小,DFA,，则,M,,所给出的等价类的个数应该是最少的最小,DFA,是不是惟一的？如果是，如何构造？,,最小,DFA,的状态对应的集合与其他,DFA,的状态对应的集合有什么样的关系，用这种关系是否能从一般的,DFA,出发，求出最小,DFA,？,40,关系,R,M,,设,DFA,M,,=( Q,,∑,,,δ,,,q,0,,,F ),M,确定的,∑,*,上的,关系,R,M,,为：,,对于,,x,,,y,∈∑,*,,,x,,R,M,,y,,,δ,(,q,0,,,x,)=,δ,(,q,0,,,y,),显然，,x,,R,M,,y,,,,,q,∈,Q,,x,,,y,∈,set(,q,),,,因此，,R,M,,决定了,∑,*,的一个分类41,例,5-8,设,,L,=0,*,10,*,，它对应的,DFA,M,,如右图所示对应于,q,0,：,(00),n,,R,M,,(00),m,,n,,,m,≥0,；,,对应于,q,1,：,0(00),n,,R,M,,0(00),m,,n,,,m,≥0,；,,对应于,q,2,：,(00),n,1,,R,M,,(00),m,1,n,,,m,≥0,；,,对应于,q,3,：,0(00),n,1,R,M,,0(00),m,1,n,,,m,≥0,；,,对应于,q,4,：,,,0(00),n,,10,k,,R,M,,0(00),m,10,h,,n,,,m,≥0,,k,,,h,≥1,；,,,(00),n,10,k,R,M,,(00),m,10,h,,n,,,m,≥0,,k,,,h,≥1,；,,,0(00),n,,10,k,R,M,,(00),m,10,h,,n,,,m,≥0,,k,,,h,≥1,；,,即：,0,n,,10,k,,R,M,,0,m,10,h,,n,,,m,≥0,,k,,,h,≥1,；,,对应于,q,5,：,x,,R,M,,y,——,x,,,y,,为至少含两个,1,的串。

42,关系,R,L,L,,确定的 ∑,*,上的关系,R,L,对于,,x,,,y,∈∑,*,，,,,x,,R,L,,y,,,(,对,,z,∈∑,*,，,xz,∈,L,,,,yz,∈,L,),,,即：对于,,x,,,y,∈∑,*,，如果,x,,R,L,,y,，则在,x,,和,y,后无论接∑,*,中的任何串,z,，,xz,和,yz,要么都是,L,,的句子，要么都不是,L,,的句子,43,关系,R,M,,与关系,R,L,如果,L,,是一个,RL,，,DFA,M,,接受的语言是,L,，对于,,q,∈,Q,，,set(,q,),中的任意两个串,x,,,y,，必有,xR,L,y,成立，即,xR,L,(,M,),,y,由于,x,,,y,∈set(,q,),，所以,δ(,q,0,,,x,)=δ(,q,0,,,y,)=,q,,对于,,z,∈∑,*,，,,,δ(,q,0,,,xz,) =δ(δ(,q,0,,,x,),,z,)),,=δ(,q,,,z,),,=δ(δ(,q,0,,,y,) ,,z,),,=δ(,q,0,,,yz,),,这就是说，,δ(,q,0,,,xz,)∈F,,δ(,q,0,,,yz,)∈F,,即对于,,z,∈∑,*,，,xz,∈,L,,,,yz,∈,L,。

表明，,x,,R,L,,y,，也就是,x,,R,L,(,M,),y,如果,xR,M,y,，则必有,xR,L,(,M,),y,如果,xR,L,(,M,),y,，则不一定有,xR,M,y,44,例,设,,L,=0,*,10,*,，它对应的,DFA,M,,如右图所示对应于,q,0,：,(00),n,,R,M,,(00),m,,n,,,m,≥0,；,,对应于,q,1,：,0(00),n,,R,M,,0(00),m,,n,,,m,≥0,；,,对应于,q,2,：,(00),n,1,,R,M,,(00),m,1,n,,,m,≥0,；,,对应于,q,3,：,0(00),n,1,R,M,,0(00),m,1,n,,,m,≥0,；,,对应于,q,4,：,0,n,,10,k,,R,M,,0,m,10,h,n,,,m,≥0,,k,,,h,≥1,；,,对应于,q,5,：,x,,R,M,,y,——,x,,,y,,为至少含两个,1,的串00,∈set(,q,0,),，,0,∈set(,q,1,),，,,0,R,M,00,不成立，但,0,R,L(M),00,成立45,右不变关系,右不变的,(right lnvariant),等价关系,,设,R,,是∑,*,上的等价关系，对于,,x,,,y,∈∑,*,，如果,x,R,y,，则必有,,xz,,R,,yz,,对于,,z,∈∑,*,成立，则称,R,是,右不变的等价关系,。

46,命题,5-1,命题,5-1,对于任意,DFA,M,= (,Q,,∑,δ,,q,0,,,F,),，,M,所确定的∑,*,上的关系,R,M,,为右不变的等价关系证明：,,(1),R,M,,是等价关系,自反性：,,因为,δ(,q,0,,,x,) =δ(,q,0,,,x,),，所以,,x,,R,M,,x,,对称性：,,x,,,y,∈∑,*,，,,,x,,R,M,,y,,,,δ(,q,0,,,x,) =δ(,q,0,,,y,),根据,R,M,,的定义；,,,δ(,q,0,,,y,) =δ(,q,0,,,x,) “=”,的对称性；,,,,y,,R,M,,x,,根据,R,M,的定义47,命题,5-1,传递性：设,x,,R,M,,y,，,y,,R,M,,z,由于,x,R,M,,y,，,δ,(,q,0,,,x,) =,δ,(,q,0,,,y,),,,由于,y,R,M,,z,，,δ,(,q,0,,,y,) =,δ,(,q,0,,,z,),,,由,“,=”,,的传递性知，,,,δ,(,q,0,,,x,) =,δ,(,q,0,,,z,),,,再由,R,M,,的定义得：,,,x,,R,M,,z,,综上，,R,M,,是等价关系。

48,命题,5-1,(2),,R,M,是右不变的,,设,x,R,M,,y,，则,δ(,q,0,,,x,)=δ(,q,0,,,y,)=,q,,,所以，对于,,z,∈∑,*,，,,,δ(,q,0,,,xz,) =δ(δ(,q,0,,,x,),,z,)),,=δ(,q,,,z,),,=δ(δ(,q,0,,,y,),,z,),,=δ(,q,0,,,yz,),,,由,R,M,,的定义，,,,xz,,R,M,,yz,,,所以，,R,M,,是右不变的等价关系49,命题,5-2,命题,5-2,对于任意,L,,∑,*,，,L,,所确定的∑,*,上的关系,R,L,,为右不变的等价关系 证明：,,(1),R,L,是等价关系自反性显然对称性：不难看出：,,,x,,R,L,,y,,,(,对,,z,∈∑,*,，,xz,∈,L,,,,yz,∈,L,),,,y,,R,L,,x,,,,传递性：设,x,,R,L,,y,，,y,,R,L,,z,x,,R,L,,y,,,(,对,,w,∈∑,*,，,xw,∈,L,,,,yw,∈,L,),,,y,,R,L,,z,,,(,对,,w,∈∑,*,，,yw,∈,L,,,,zw,∈,L,),,,所以，,(,,w,∈∑,*,,,xw,∈,L,,,,yw,∈,L,,且,yw,∈,L,,,,zw,∈,L,),,,即：,(,对,,w,∈∑,*,，,xw,∈,L,,zw,∈,L,),,,故：,x,,R,L,,z,,,即,R,L,,是等价关系。

50,命题,5-2,(2),R,L,,是右不变的设,x,R,L,,y,由,R,L,的定义，对,,w,,,v,∈∑,*,，,,,xwv,∈,L,,,,zwv,∈,L,，注意到,v,的任意性，知,,,xw,R,L,yw,所以，,R,L,,是右不变的等价关系51,指数,(index),设,R,是∑,*,上的等价关系，则称,|∑,*,/,R,|,是,R,关于∑,*,的指数,简称为,R,的,指数,∑,*,的关于,R,的一个等价类，也就是∑,*,/,R,,的任意一个元素，简称为,R,的一个等价类,52,例,5-9,右图所给,DFA,M,,所确定的,R,M,,的指数为,6,R,M,,将∑,*,分成,6,个等价类：,,,set(,q,0,)={ (00),n,,|,n,≥,0 },；,,,set(,q,1,)={ 0(00),n,,|,n,≥,0 },；,,,set(,q,2,)={ (00),n,1,,|,,n,,,m,≥,0 },；,,,set(,q,3,)={ 0(00),n,,1|,n,≥,0 },；,,,set(,q,4,)={ 0,n,10,k,,|,n,≥,0, k,≥,1 },；,,,set(,q,5,)={,x,|,x,为至少含两个,1,的串,},。

53,R,M,,与,R,L,(,M,),,x,,,y,∈∑,*,，如果,x R,M,y,，必有,xR,L,(,M,),y,,成立对于任意,DFA,M,=(Q,∑,δ,,q,0,, F),：,,(1),|∑,*,/,R,L,(,M,),|≤|∑,*,/,R,M,|≤|Q|,,,(2),按照,R,M,中被分在同一等价类的串，在按照,R,L,(,M,),分类时，一定会被分在同一个等价类R,M,对 ∑,*,的划分比,R,L,(,M,),对 ∑,*,的划分更“细”称,R,M,是,R,L,(,M,),的“加细”,(refinement),54,问题讨论,在∑,*,/,R,M,={ set(,q,0,), set(,q,1,), set(,q,2,), set(,q,3,), set(,q,4,), set(,q,5,) },中，,,是否存在有根据,R,L,(,M,),可以“合并” 的等价类？,,(1),取,00∈set(,q,0,),，,000∈set(,q,1,),对于任意的,x,∈∑,*,，,,当,x,,含且只含一个,1,时，,00,x,∈,L,(,M,),，,000,x,∈,L,(,M,),；,,当,x,,不含,1,或者含多个,1,时，,00,x,,L,(,M,),，,000,x,,L,(,M,),。

这就是说，对于任意,x,∈∑,*,，,00,x,∈,L,(,M,),,000,x,∈,L,(,M,),即按照,R,L,(,M,),，,00,与,000,被分在同一个等价类中从而,set(,q,0,),和,set(,q,1,),被包含在,R,L,(,M,),的同一个等价类中55,问题讨论,(2),取,00∈set(,q,0,),，,001∈set(,q,2,),取特殊的字符串,1∈∑,*,，,001∈,L,(,M,),，但,0011,,L,(,M,),所以，根据,R,L,(,M,),，,set(,q,0,),和,set(,q,2,),不能被“合并”到一个等价类中类似地，根据,R,L,(,M,),，,set(,q,3,),、,set(,q,4,),、,set(,q,5,),也都不能被“合并”到,set(,q,0,),的句子所在的等价类中3),取,001∈set(,q,2,),，,01∈set(,q,3,),对于任意的,x,∈∑,*,，,x,要么不含,1,，要么含有,1,当,x,不含,1,时，,001,x,∈,L,(,M,),，,01,x,∈,L,(,M,),；,,当,x,,含有,1,时，,001,x,,L,(,M,),，,01,x,,L,(,M,),。

这就是说，对于任意,x,∈∑,*,，,001,x,∈,L,(,M,),,01,x,∈,L,(,M,),即按照,R,L,(,M,),，,001,与,01,属于,R,L,(,M,),的同一个等价类中从而,set(,q,2,),和,set(,q,3,),被包含在,R,L,(,M,),的同一个等价类中56,问题讨论,(4),取,1∈set(,q,2,),，,10∈set(,q,4,),对于任意的,x,∈∑,*,，,x,要么不含,1,，要么含有,1,当,x,,不含,1,时，,1,x,∈,L,(,M,),，,10,x,∈,L,(,M,),；,,当,x,含有,1,时，,1,x,,L,(,M,),，,10,x,,L,(,M,),这就是说，对于任意的,x,∈∑,*,，,1,x,∈,L,(,M,),,10,x,∈,L,(,M,),即按照,R,L,(,M,),，,1,与,10,被分在,R,L,(,M,),的同一个等价类中从而在,set(,q,2,),和,set(,q,4,),被包含在,R,L,(,M,),的同一个等价类中5),取,1∈set(,q,2,),，,11∈set(,q,5,),注意到,1ε=1,，,11ε=11,；而,1∈,L,(,M,),，,11,,L,(,M,),。

即,1,和,11,不满足关系,R,L,(,M,),，所以，,set(,q,2,),和,set(,q,5,),不能被“合并”到,R,L,(,M,),的同一个等价类中在这里，,ε∈∑,*,是一个特殊的字符串57,问题讨论,∑,*,/,R,L,(,M,),={ set(,q,0,)∪set(,q,1,),，,set(,q,2,)∪set(,q,3,)∪set(,q,4,),，,set(,q,5,)},,不含,1,：,,,[0]= set(,q,0,)∪set(,q,1,) = 0,*,；,,含一个,1,：,,,[1]= set(,q,2,)∪set(,q,3,)∪set(,q,4,) = 0,*,10,*,；,,含多个,1,：,,,[11]= set(,q,5,) = 0,*,10,*,1(0+1),*,58,Myhill-Nerode,定理,米希尔,-,尼德罗定理,,如下三个命题等价：,,(1),L,,∑,*,是,RL,2),L,是 ∑,*,上的某一个具有有穷指数的右不变等价关系,R,,的某些等价类的并3),R,L,,具有有穷指数59,由,(1),可以推出,(2),(1),L,,∑,*,是,RL,,。

2),L,是 ∑,*,上的某一个具有有穷指数的右不变等价关系,R,,的某些等价类的并设,L,,∑,*,是,RL,，,,所以，存在,DFA,M,= (,Q,,∑,δ,,q,0,,,F,),，使得,L,(,M,)=,L,由命题,5-1,，,R,M,,是 ∑,*,上的右不变等价关系，,,而且,|∑,*,/,R,M,|≤| Q |,，所以，,R,M,具有有穷指数而,即,L,,是 ∑,*,上的具有有穷指数的右不变等价关系,R,M,的、对应于,M,的终止状态的等价类的并60,由,(2),可以推出,(3),(2),L,,是 ∑,*,上的某一个具有有穷指数的右不变等价关系,R,,的某些等价类的并,3),R,L,具有有穷指数,设,x,R,y,，由,R,,的右不变性可知，对于任意,z,∈∑,*,，,,,xz,R,yz,,,而,L,,是,R,,的某些等价类的并，所以,,,xz,∈,L,,,,yz,∈,L,,,根据,R,L,,的定义，,,,x,R,L,,y,,,故,R,,是,R,L,,的加细由于,R,,具有有穷指数，所以，,R,L,,具有有穷指数61,由,(3),可以推出,(1),(3),R,L,,具有有穷指数,。

1),L,,∑,*,是,RL,,设,R,L,,具有有穷指数往证,存在,DFA,M',，使得,L,(,M',)=,L,思路是,用等价类对应状态，状态之间的转移依据相应的等价类的变化,令,M,',=(∑,*,/,R,L,, ∑, δ,',, [ε], {,[,x,],|,x,∈,L,}),,[ε],表示,ε,所在的等价类对应的状态；,,,[,x,],表示,x,,所在的等价类对应的状态对于,,([,x,],,a,)∈(∑,*,/,R,L,)×∑,,δ,',([,x,],,a,) = [,xa,],,δ,',定义具有,相容性,,(,如果,[,x,]=[,y,],，那么,[,xa,]=[,ya,],),,,如果,x,,和,y,,同处一个等价类，即,[,x,]=[,y,],，有,x,R,L,y,，,,由,R,L,,的右不变性，有,xa,R,L,ya,,,即,[,xa,]=[,ya,],因此，,L,(,M,',)=,L,62,例,5-10,用定理,5-7,证明,{ 0,n,1,n,|,n,≥0 },不是,RL,思路：,根据,L,的句子的特征来寻找,R,L,的等价类L,,的句子的主要特点有两个：,,(1),句子中所含的字符,0,的个数与所含的字符,1,的个数相同。

2),所有的,0,都在所有的,1,的前面由此可知，对所有的串,x,，如果,x,是,0,n,1,m,(,m,≥,n,+1),，或者,x,中含有子串,10,，则无论,x,后面接任何串,z,，都有,xz,不属于,L,将此等价类记为,[10],再考虑形如,0,n,形如,0,n,1,m,的串，,m,,,n,≥0,且,n,≥,m,注意到,01,∈,L,，,001,,L,，所以,0,和,00,不在同一个等价类中,可以得到如下一些等价类63,例,5-10,[10]={,x,|,x,=0,n,1,m,(,m,≥,n,+1),或者,x,中含子串,10 },,[ε]——ε,所在的等价类；,,[1]——0,所在的等价类；,,[2]——00,所在的等价类；,,[3]——000,所在的等价类；,,…,,[,n,]——0,n,,所在的等价类；,,…,,所以，,R,L,,的指数是无穷的因此，,L,不是,RL,64,Myhill-Nerode,定理的推论,推论,5-2,对于任意的,RL,L,，如果,DFA,M,=(Q,∑,δ,,q,0,, F),满足,L,(,M,)=,L,，则,|∑,*,/,R,L,|≤|Q|,即,对于任意,DFA,M,=(Q,∑,δ,,q,0,, F),，,|Q|≥|∑,*,/,R,L,(,M,),|,。

也表明，,对任意一个,RL,L,，按照定理,5-7,中所给的方法构造出来的,DFA,M,',,是一个接受,L,的最小,DFA,问题：这个,DFA,是惟一的么？,,推论,5-3,对于任意的,RL,L,，在同构意义下，接受,L,,的最小,DFA,是惟一的接受,L,,的最小,DFA,M,=(Q,∑, δ,,q,0,, F),,,定理,5-7,构造的,DFA,M',,=(∑,*,/,R,L,, ∑, δ,',, [ε], {[,x,] |,x,∈,L,}),,,M,与,M',同构，是指二者的状态数一一对应，状态转移也是一一对应的定义映射：,f,(,q,)=,f,(δ(,q,0,,,x,) )= δ,',( [ε],,x,)=[,x,],,,即让,M',的状态,[,x,],与,M,的状态,q,=δ(,q,0,,,x,),对应,， 该状态正是,x,引导,M,,从,q,0,出发所到达的状态65,推论,5-3,推论,5-3,对于任意的,RL,L,，在同构意义下，接受,L,,的最小,DFA,是惟一的证明：,,接受,L,的最小,DFA,M,= (Q,∑,δ,,q,0,, F),的状态数与,R,L,的指数相同，也就是说，这个最小,DFA,的状态数与,Myhill-Nerode,定理证明中构造的,M',,=(∑,*,/R,L,,∑,δ,',, [ε], {[,x,] |,x,∈,L,} ),的状态数是相同的。

DFA,同构是指这两个,DFA,的状态之间有一个一一对应，而且这个一一对应还保持状态转移也是相应一一对应的也就是说，如果,q,,与,[,w,],对应，,p,与,[,z,],对应，当,δ(,q,,,a,)=,p,时，必定有,δ([,w,],,a,)=[,z,],这两个,DFA,是同构定义映射,f,,,,f,(,q,)=,f,(δ(,q,0,,,x,) )= δ,',( [ε],,x,)=[,x,],,,即让,M',的状态,[x],与,M,,的状态,q,=δ(,q,0,,,x,),对应， 该状态正是,x,,引导,M,,从,q,0,出发所到达的状态66,推论,5-3,往证,f,为,Q,与 ∑,*,/,R,L,之间的一一对应如果,δ,(,q,0,,,x,)=,δ,(,q,0,,,y,),，则,x,R,M,,y,,由于,R,M,,是,R,L,,的加细，所以，,x,R,L,,y,,故，,[,x,]=[,y,],，,即,δ,',([,ε,],,x,)=,δ,',([,ε,],,y,),如果,δ,(,q,0,,,x,),≠δ,(,q,0,,,y,),,则,δ,',([,ε,],，,x,),≠δ,',([,ε,],,y,),,即,[,x,],≠,[,y,],,否则,|,∑,*,/,R,M,|>|,∑,*,/,R,L,|,。

这与,M,,是最小,DFA,矛盾所以，,f,是,Q,与,∑,*,/,R,L,之间的一一对应67,推论,5-3,往证，如果,δ,(,q,,,a,)=,p,，,f,(,q,)=,f,(,δ,(,q,0,,,x,))=[,x,],，,,由于,δ,',([,ε,],,xa,)=[,xa,],，因此,必有,f,(,p,)=[,xa,],事实上，对于,,q,∈,Q,，,,如果,f,(,q,) =,f,(,δ,(,q,0,,,x,))=[,x,],,则对于 ,a,∈∑,，如果,,,p,=,δ,(,q,,,a,)=,δ,(,δ,(,q,0,,,x,),,a,)=,δ,(,q,0,,,xa,),,则,f,(,p,)=,f,(,δ,(,q,,,a,))=,f,(,δ,(,δ,(,q,0,,,x,),,a,))=,f,(。