形式语言与自动机理论电子教案-05.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第5章 RL的性质,RL,性质,泵引理及其应用,并、乘积、闭包、补、交,正则代换、同态、逆同态的封闭性,从RL,固有特征寻求表示的一致性,Myhill-Nerode,定理,FA,的极小化,RL,的几个判定问题,空否、有穷否、两个,DFA,等价否、成员关系,1/29/2026,1,5.1 RL的泵引理,泵引理(,pumping lemma),设,L,为一个,RL,，则存在仅依赖于,L,的正整数,N,，对于,z,L,，如果,|z|,N,，则存在,u,、,v,、,w,，满足,z=uvw；,|uv|N；,|v|1；,对于任意的整数i0，uv,i,wL；,N不大于接受L的最小DFA M的状态数。,1/29/2026,2,5.1 RL的泵引理,证明思想,1/29/2026,3,5.1 RL的泵引理,证明：,DFA在处理一个足够长的句子的过程中，必定会重复地经过某一个状态。换句话说，在DFA的状态转移图中，必定存在一条含有回路的从启动状态到某个终止状态的路。由于是回路，所以，DFA可以根据实际需要沿着这个回路循环运行，相当于这个回路中弧上的标记构成的非空子串可以重复任意多次。,1/29/2026,4,5.1 RL的泵引理,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,1/29/2026,5,5.1 RL的泵引理,(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,对于任意的整数,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,1/29/2026,6,5.1 RL的泵引理,故，,(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=a,1,a,2,a,k,，,v=a,k+1,a,j,，,w=a,j+1,a,m,uv,i,w,L,1/29/2026,7,5.1 RL的泵引理,例 5-1,证明,0,n,1,n,|n,1,不是,RL。,证明：,假设,L=0,n,1,n,|n,1,是,RL,z=0,N,1,N,按照泵引理所述,v=0,k,k,1,此时有，,u=0,N-k-j,w=0,j,1,N,1/29/2026,8,5.1 RL的泵引理,从而有，,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+kN,。,这就是说，,0,N+k,1,N,L,这与泵引理矛盾。所以，,L,不是,RL。,1/29/2026,9,5.1 RL的泵引理,例 5-2,证明,0,n,|n,为素数,不是,RL。,证明：假设,L=0,n,|n,为素数,是,RL。,取,z=0,N+p,L，,不妨设,v=0,k,，,k,1,从而有，,uv,i,w=0,N+p-k-j,(0,k,),i,0,j,=0,N+p+(i-1)k,1/29/2026,10,5.1 RL的泵引理,当,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。,1/29/2026,11,5.1 RL的泵引理,例 5-3,证明0,n,1,m,2,n+m,|m，n1不是 RL。,证明：假设L=0,n,1,m,2,n+m,|m，n1 是 RL。,取z=0,N,1,N,2,2N,设v=0,k,k1,从而有，,uv,i,w=0,N-k-j,(0,k,),i,0,j,1,N,2,2N,=0,N+(i-1)k,1,N,2,2N,1/29/2026,12,5.1 RL的泵引理,uv,0,w=0,N+(0-1)k,1,N,2,2N,=0,N-k,1,N,2,2N,注意到k1，,N-k+N=2N-k|,*,/R,L,|。,1/29/2026,78,5.3.1 Myhill-Nerode 定理,如果,(q,，,a)=p,，,f(q)=x,，必有,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(,(q,0,，,xa)=xa,即，如果,M,在状态,q,读入字符,a,时进入状态,p,，则,M,在,q,对应的状态,f(,(q,0,，,x)=x,读入字符,a,时，进入,p,对应的状态,f(,(q,0,，,xa)=xa,。所以，,f,是,M,和,M,之间的同构映射。,1/29/2026,79,5.3.2 DFA的极小化,可以区分的,(distinguishable),状态,设,DFA M=(Q,，,q,0,，,F),，如果,x,*,，,对,Q,中的两个状态,q,和,p,，使得,(q,，,x),F,和,(p,，,x),F,中，有且仅有一个成立，则称,p,和,q,是,可以区分的,。否则，称,q,和,p,等价。并记作,q,p,。,1/29/2026,80,5.3.2 DFA的极小化,算法5-1,DFA,的极小化算法,算法思想：扫描所有的状态对，找出所有的可区分的状态对，不可取分的状态对一定是等价的。,输入：给定的,DFA。,输出：可区分状态表。,主要数据结构：状态对的关联链表；可区分状态表。,1/29/2026,81,5.3.2 DFA的极小化,主要步骤,for,(q,，,p),F,(Q-F),do,标记可区分状态表中的表项,(q,，,p),；,for,(q,p),F,F,(Q-F),(Q-F)&q,p,do,if,a,，可区分状态表中的表项,(,(q,，,a),，,(p,，,a),已被标记,then,begin,标记可区分状态表中的表项,(q,，,p),；,递归地标记本次被标记的状态对的关联链表上的各个状态对在可区分状态表中的对应表项,end,1/29/2026,82,5.3.2 DFA的极小化,else for,a,，,do,if,(q,，,a),(p,，,a)&(q,，,p),与,(,(q,，,a),，,(p,，,a),不是同一个状态对,then,将,(q,，,p),放在,(,(q,，,a),，,(p,，,a),的关联链表上。,1/29/2026,83,5.3.2 DFA的极小化,定理5-8,对于任意,DFA M=(Q,，,q,0,，,F),，,Q,中的两个状态,q,和,p,是可区分的充要条件是,(q,，,p),在,DFA,的极小化算法中被标记。,证明：,先证必要性。,设,q,和,p,是可区分的，,x,是区分,q,和,p,的最短字符串。现施归纳于,x,的长度，证明,(q,，,p),一定被算法标记。,1/29/2026,84,5.3.2 DFA的极小化,当,|x|=0,时,区分,q,和,p,，表明,q,和,p,有且仅有一个为,M,的终止状态，所以，,(q,，,p),F,(Q-F),因此，它在算法的第,(1),行被标记。,设当,|x|=n,时结论成立,x,是区分,q,和,p,的长度为,n,的字符串，则,(q,，,p),被算法标记。,1/29/2026,85,5.3.2 DFA的极小化,当,|x|=n+1,时,设,x=ay,，其中,|y|=n,。由于,x,是区分,q,和,p,的最短的字符串，所以，,(q,，,x),F,和,(p,，,x),F,中，有且仅有一个成立。不妨假设：,(q,，,x),F,，,(p,，,x),F,即,(,(q,，,a),，,y),F,，,(,(p,，,a),，,y),F,设,(q,，,a)=u,，,(p,，,a)=v,y,是区分,u,和,v,的长度为,n,的字符串。,1/29/2026,86,5.3.2 DFA的极小化,由归纳假设，,(u,，,v),可以被算法标记,。,如果在考察,(q,，,p),时，,(u,，,v),已经被标记，则,(q,，,p),在算法的第,(4),行被标记；,如果在考察,(q,，,p),时，,(u,，,v),还没有被标记，则,(q,，,p),在算法的第,(7),行被放入到,(u,，,v),的关联链表中，而当,(u,，,v),被标记时，在算法的第,(5),行在,“,递归,”,过程中,(q,，,p),被标记。,结论对,|x|=n+1,成立。,1/29/2026,87,5.3.2 DFA的极小化,充分性。,设,(q,，,p),在算法中被标记。对它被标记的顺序,n,施归纳，证明,q,和,p,是可区分的。,令,|F,(Q-F)|=m,，显然，当,1,n,m,时，,(q,，,p),是在算法的第,(1),行被标记的，此时，是区分,q,和,p,的字符串：,(q,，,),F,和,(p,，,),F,有且仅有一个成立。,1/29/2026,88,5.3.2 DFA的极小化,设,n,k(k,m),时结论成立。即，如果,(q,，,p),是被算法在第,k,个或者第,k,个之前标记的，则存在字符串,x,，,x,区分,q,和,p,。即：,(q,，,x),F,和,(p,，,x),F,有且仅有一个成立。,当,n=k+1,时，如果,(q,，,p),是在算法的第,(4),行被标记的，此时，,(,(q,，,a),，,(p,，,a),一定是在第,k,个之前被标记的。设,(q,，,a)=u,，,(p,，,a)=v,，由归纳假设，存在字符串,x,，,x,区分,u,和,v,：,(u,，,x),F,和,(v,，,x),F,有且仅有一个成立，从而，,(q,，,ax),F,和,(p,，,ax),F,有且仅有一个成立。即，,ax,是区分,q,和,p,的字符串。,1/29/2026,89,5.3.2 DFA的极小化,如果,(q,，,p),是在算法的第,(5),行被标记的，则它必在某个状态对,(u,，,v),的关联链表中，而,(u,，,v),必在,(q,，,p),之前被标记。由归纳假设，存在,x,区分,(u,，,v),；,存在,a,，,(q,，,a)=u,，,(p,，,a)=v,使得,(q,，,p),被放在,(u,，,v),的关联链表中；,ax,是区分,q,和,p,的字符串。,所以，结论对,n=k+1,成立。由归纳法原理，结论对所有的,n,成立。,1/29/2026,90,5.3.2 DFA的极小化,定理5-9,由算法,5-1,构造的,DFA,在去掉不可达状态是最小,DFA,。,证明：,设,M=(Q,q,0,F),为算法,5-1,的输入,DFA,，,M,=(Q/,q,0,F,),是相应的输出,DFA,。,F,=q|q,F,。,对于,q,Q/,，,a,，定义,(q,，,a)=,(q,，,a),1/29/2026,91,5.3.2 DFA的极小化,的相容性。,设,q=p,，也就是说，,q,和,p,等价：,q,p,。即根据算法,5-1,，状态,q,和,p,是不可区分的,(,未被算法标记,),。此时，对于,a，必须有,(q,，,a),(p,，,a),。否则，状态对,(,(q,，,a),，,(p,，,a),必定被算法标记，从而最终导致,(q,，,p),被算法标记。此与,q,p,矛盾。所以，状态,(q,，,a),和状态,(p,，,a),等价：,(q,，,a)=,(p,，,a),。所以，的定义是相容的。,1/29/2026,92,5.3.2 DFA的极小化,L(M,)=L(M),。,对,x,*,，现施归纳于,|x|,，证明,(q,0,，,x)=,(q,0,，,x),|x|=0,(q,0,，,)=q,0,=,(q,0,，,),x,*,并且,|x|=n,，,(q,0,，,xa)=,(,(q,0,，,x),，,a),=,(,(q,0,，,x),，,a),=,(,(q,0,，,x),，,a),=,(q,0,，,xa),由归纳法原理，结论对,x,*,成立。,1/29/2026,93,5.3.2 DFA的极小化,再由,F,的定义，,(q,0,，,x)=,(q,0,，,x),F,(q,0,，,x),F,。,所以，,x,L(M,),x,L(M),。,即：,L(M,)=L(M)。,1/29/2026,94,5.3.2 DFA的极小化,证明所构造的,M,去掉不可达状态后是最小,DFA,。,如果,q,p,，则对于,x,set(q),，,y,set(p),，,x R,L,y,不成立。事实上，如果,q,p,，则存在,z,*,，,z,区分,q,和,p,，有,(q,，,z)=q,和,(p,，,z)=p,有且仅有一个是终止状态，这就是说，,xz,和,yz,有且仅有一个是,L,的句子。所以，,x R,L,y,是不成立的。,1/29/2026,95,5.3.2 DFA的极小化,例5-11,用算法,5-1,对图,5-4,所给的,DFA,进行极小化。,q,1,q,2,q,3,q,4,q,5,q,0,q,1,q,2,q,3,q,4,1/29/2026,96,5.3.2 DFA的极小化,1/29/2026,97,5.3.2 DFA的极小化,例5-11,用算法,5-1,对图,5-7,所给的,DFA,进行极小化。,1/29/2026,98,5.3.2 DFA的极小化,q,1,q,2,q,3,q,4,q,5,q,6,q,7,q,8,q,0,q,1,q,2,q,3,q,4,q,5,q,6,q,7,1/29/2026,99,5.4 关于正则语言的判定算法,定理 5-10,设,DFA M=(Q,，,q,0,，,F),，,L=L(M),非空的充分必要条件是：存在,x,*,，,|x|Q|,，,(q,0,，,x),F。,证明：充分性显然。,必要性：,M,的状态转移图中必存在一条从,q,0,到某一个终止状态,q,f,且无,重复状态的路，此路中的状态数,n,|Q|,。此路的标记,x,满足,|x|,n-1,。而,(q,0,，,x),F,。即,x,是,L=L(M),的长度小于,|Q|,的句子。,1/29/2026,100,5.4 关于正则语言的判定算法,定理5-11,设,DFA M=(Q,，,q,0,，,F),，,L=L(M),为无穷的充分必要条件是：存在,x,*,，,|Q|,|x|2|Q|,，,(q,0,，,x),F。,算法通过判定是否存在,x,*,，,|Q|,|x|2|Q|,，,(q,0,，,x),F,即可。,1/29/2026,101,5.4 关于正则语言的判定算法,定理 5-12,设,DFA M,1,=(Q,1,，,1,，,q,01,，,F,1,),，,DFA M,2,=(Q,2,，,2,，,q,02,，,F,2,),，则存在判定,M,1,与,M,2,是否等价的算法。,通过判定两个DFA的极小DFA是否同构就可以判定它们是否等价。,1/29/2026,102,5.4 关于正则语言的判定算法,定理 5-13,设,L,是字母表上的,RL,，对任意,x,*,，存在判定,x,是不是,L,的句子的算法。,从一定的意义上讲，接受,L,的,DFA M就是判定x是否L的一个桔子的“算法”。,1/29/2026,103,5.5 小结,本章讨论了,RL,的性质。包括：,RL,的泵引理，,RL,关于并、乘积、闭包、补、交、正则代换、同态、逆同态等运算的封闭性。,Myhill-Nerode,定理与,FA,的极小化。,泵引理。泵引理是用,RL,的必要条件来用来证明一个语言不是,RL,的。它不能用来证明一个语言是,RL,，而且是采用反证法。,1/29/2026,104,5.5 小结,RL,对有关运算的封闭性。,RL,在并、乘、闭包、补、交、正则代换、同态映射运算下是有效封闭的。,RL,的同态原像是,RL,。,设,L,1,、,L,2,*,，如果,L,1,是,RL,，则,L,1,/L,2,也是,RL,。,1/29/2026,105,5.5 小结,如果,L,是,RL,，则根据,R,L,确定的,*,的等价类可以构造出接受,L,的最小,DFA,。更方便的方法是通过确定给定,DFA,状态的可区分性构造出等价的最小,DFA,。,存在判定,L(M),是非空、,M,1,与,M,2,是否等价、,L(M),是否无穷、,x,是不是,RL L,的句子的算法。,1/29/2026,106,