形式语言与自动机理论电子教案-05省名师优质课赛课获奖课件市赛课百校联赛优质课一等奖课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。,第5章 RL性质,RL性质,泵引理及其应用,并、乘积、闭包、补、交,正则代换、同态、逆同态封闭性,从RL,固有特征寻求表示一致性,Myhill-Nerode,定理,FA,极小化,RL,几个判定问题,空否、有穷否、两个,DFA,等价否、组员关系,1/106,3/17/2025,1,5.1 RL泵引理,泵引理(,pumping lemma),设L为一个 RL，则存在仅依赖于L正整数N，对于,zL，假如|z|N，则存在u、v、w，满足,z=uvw；,|uv|N；,|v|1；,对于任意整数i0，uv,i,wL；,N小于接收L最小DFA M状态数。,2/106,3/17/2025,2,5.1 RL泵引理,证实思想,3/106,3/17/2025,3,5.1 RL泵引理,证实：,DFA在处理一个足够长句子过程中，必定会重复地经过某一个状态。换句话说，在DFA状态转移图中，必定存在一条含有回路从开启状态到某个终止状态路。因为是回路，所以，DFA能够依据实际需要沿着这个回路循环运行，相当于这个回路中弧上标识组成非空子串能够重复任意屡次。,4/106,3/17/2025,4,5.1 RL泵引理,M=(Q，q,0,，F),|Q|=N,z=a,1,a,2,a,m,mN,(q,0,，a,1,a,2,a,h,)=q,h,状态序列q,0,，q,1,，q,N,中，最少有两个状态是相同：q,k,=q,j,5/106,3/17/2025,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,对于任意整数i0,(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,6/106,3/17/2025,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,wL,7/106,3/17/2025,7,5.1 RL泵引理,例 5-1,证实0,n,1,n,|n1不是 RL。,证实：,假设L=0,n,1,n,|n1 是 RL,z=0,N,1,N,按照泵引理所述,v=0,k,k1,此时有，,u=0,N-k-j,w=0,j,1,N,8/106,3/17/2025,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,注意到k1，所以，,N+kN。,这就是说，,0,N+k,1,N,L,这与泵引理矛盾。所以，L不是 RL。,9/106,3/17/2025,9,5.1 RL泵引理,例 5-2,证实0,n,|n为素数不是 RL。,证实：假设L=0,n,|n为素数 是 RL。,取 z=0,N+p,L，,不妨设v=0,k,，k1,从而有，,uv,i,w=0,N+p-k-j,(0,k,),i,0,j,=0,N+p+(i-1)k,10/106,3/17/2025,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),注意到k1，所以,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。,11/106,3/17/2025,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,12/106,3/17/2025,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,|。,78/106,3/17/2025,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,之间同构映射。,79/106,3/17/2025,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,。,80/106,3/17/2025,80,5.3.2 DFA极小化,算法5-1,DFA,极小化算法,算法思想：扫描全部状态对，找出全部可区分状态对，不可取分状态对一定是等价。,输入：给定,DFA。,输出：可区分状态表。,主要数据结构：状态正确关联链表；可区分状态表。,81/106,3/17/2025,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,82/106,3/17/2025,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),关联链表上。,83/106,3/17/2025,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),一定被算法标识。,84/106,3/17/2025,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),被算法标识。,85/106,3/17/2025,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,字符串。,86/106,3/17/2025,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,成立。,87/106,3/17/2025,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,有且仅有一个成立。,88/106,3/17/2025,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,字符串。,89/106,3/17/2025,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,成立。,90/106,3/17/2025,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),91/106,3/17/2025,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),。所以，定义是相容。,92/106,3/17/2025,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,*,成立。,93/106,3/17/2025,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)。,94/106,3/17/2025,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,是不成立。,95/106,3/17/2025,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,96/106,3/17/2025,96,5.3.2 DFA极小化,97/106,3/17/2025,97,5.3.2 DFA极小化,例5-11,用算法,5-1,对图,5-7,所给,DFA,进行极小化。,98/106,3/17/2025,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,99/106,3/17/2025,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|,句子。,100/106,3/17/2025,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,即可。,101/106,3/17/2025,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是否同构就能够判定它们是否等价。,102/106,3/17/2025,102,5.4 关于正则语言判定算法,定理 5-13,设,L,是字母表上,RL,，对任意,x,*,，存在判定,x,是不是,L,句子算法。,从一定意义上讲，接收,L,DFA M就是判定x是否L一个桔子“算法”。,103/106,3/17/2025,103,5.5 小结,本章讨论了,RL,性质。包含：,RL,泵引理，,RL,关于并、乘积、闭包、补、交、正则代换、同态、逆同态等运算封闭性。,Myhill-Nerode,定理与,FA,极小化。,泵引理。泵引理是用,RL,必要条件来用来证实一个语言不是,RL,。它不能用来证实一个语言是,RL,，而且是采取反证法。,104/106,3/17/2025,104,5.5 小结,RL,对相关运算封闭性。,RL,在并、乘、闭包、补、交、正则代换、同态映射运算下是有效封闭。,RL,同态原像是,RL,。,设,L,1,、,L,2,*,，假如,L,1,是,RL,，则,L,1,/L,2,也是,RL,。,105/106,3/17/2025,105,5.5 小结,假如,L,是,RL,，则依据,R,L,确定,*,等价类能够结构出接收,L,最小,DFA,。更方便方法是经过确定给定,DFA,状态可区分性结构出等价最小,DFA,。,存在判定,L(M),是非空、,M,1,与,M,2,是否等价、,L(M),是否无穷、,x,是不是,RL L,句子算法。,106/106,3/17/2025,106,