《形式语言与自动机理论电子教案-05》由会员分享，可在线阅读，更多相关《形式语言与自动机理论电子教案-05（106页珍藏版）》请在金锄头文库上搜索。
1、2018/2/14,1,第5章 RL的性质,RL性质 泵引理及其应用 并、乘积、闭包、补、交正则代换、同态、逆同态的封闭性 从RL固有特征寻求表示的一致性Myhill-Nerode定理FA的极小化 RL的几个判定问题空否、有穷否、两个DFA等价否、成员关系,2018/2/14,2,5.1 RL的泵引理,泵引理(pumping lemma) 设L为一个 RL ，则存在仅依赖于L的正整数N，对于zL，如果|z|N，则存在u、v、w，满足 z=uvw； |uv|N； |v|1； 对于任意的整数i0，uviwL； N不大于接受L的最小DFA M的状态数。,2018/2/14,3,5.1 RL的泵引理,
2、证明思想,2018/2/14,4,5.1 RL的泵引理,证明：DFA在处理一个足够长的句子的过程中，必定会重复地经过某一个状态。换句话说，在DFA的状态转移图中，必定存在一条含有回路的从启动状态到某个终止状态的路。由于是回路，所以，DFA可以根据实际需要沿着这个回路循环运行，相当于这个回路中弧上的标记构成的非空子串可以重复任意多次。,2018/2/14,5,5.1 RL的泵引理,M=(Q，q0，F) |Q|=N z= a1a2ammN (q0，a1a2ah)=qh 状态序列q0，q1，qN中，至少有两个状态是相同：qk=qj,2018/2/14,6,5.1 RL的泵引理,(q0，a1a2ak)
3、=qk(qk，ak+1aj)=qj=qk(qj，aj+1am)=qm对于任意的整数i0 (qk，(ak+1aj)i)=(qk，(ak+1aj)i-1)=(qk，ak+1aj)=qk,2018/2/14,7,5.1 RL的泵引理,故，(q0，a1a2ak(ak+1aj)i aj+1am)=qm也就是说， a1a2ak(ak+1aj)i aj+1amL(M) u= a1a2ak，v=ak+1aj，w= aj+1am uviwL,2018/2/14,8,5.1 RL的泵引理,例 5-1 证明0n1n|n1不是 RL。 证明： 假设L=0n1n|n1 是 RL z=0N1N 按照泵引理所述 v=0kk
4、1 此时有，u=0N-k-jw=0j1N,2018/2/14,9,5.1 RL的泵引理,从而有，uviw=0N-k-j(0k)i0j1N=0N+(i-1)k1N 当i=2时，我们有：uv2w=0N+(2-1)k1N = 0N+k1N注意到k1，所以，N+kN。这就是说，0N+k1NL这与泵引理矛盾。所以，L不是 RL。,2018/2/14,10,5.1 RL的泵引理,例 5-2 证明0n|n为素数不是 RL。 证明：假设L=0n|n为素数 是 RL。 取 z=0N+p L ，不妨设v=0k，k1 从而有，uviw=0N+p-k-j(0k)i0j=0N+p+(i-1)k,2018/2/14,11
5、,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时，uvN+p+1w=0(N+p)(1+k) L这与泵引理矛盾。所以，L不是 RL。,2018/2/14,12,5.1 RL的泵引理,例 5-3 证明0n1m2n+m|m，n1不是 RL。 证明：假设L=0n1m2n+m|m，n1 是 RL。 取z=0N1N22N 设v=0k k1 从而有，uviw=0N-k-j(0k)i0j1N22N=0N+(i-1)k1
6、N22N,2018/2/14,13,5.1 RL的泵引理,uv0w=0N+(0-1)k1N22N= 0N-k1N22N 注意到k1，N-k+N=2N-k2N0N-k1N22N L这个结论与泵引理矛盾。所以，L不是 RL。,2018/2/14,14,5.1 RL的泵引理,用来证明一个语言不是 RL不能用泵引理去证明一个语言是 RL。 由于泵引理给出的是 RL 的必要条件，所以，在用它证明一个语言不是 RL 时，我们使用反证法。 泵引理说的是对 RL 都成立的条件，而我们是要用它证明给定语言不是 RL ，这就是说，相应语言的“仅仅依赖于L的正整数N”实际上是不存在的。所以，我们一定是无法给出一个具
7、体的数的。因此，人们往往就用符号N来表示这个“假定存在”、而实际并不存在的数。,2018/2/14,15,5.1 RL的泵引理, 由于泵引理指出，如果L是 RL ，则对任意的zL，只要|z|N，一定会存在u、v、w，使uviwL对所有的i成立。因此，我们在选择z时，就需要注意到论证时的简洁和方便。 当一个特意被选来用作“发现矛盾”的z确定以后，就必须依照|uv|N和|v|1的要求，说明v不存在(对“存在u、v、w”的否定) 。,2018/2/14,16,5.1 RL的泵引理, 与选z时类似，在寻找i时，我们也仅需要找到一个表明矛盾的“具体”值就可以了(对“所有i”的否定)。 一般地，在证明一个
8、语言不是 RL 的时候，我们并不使用泵引理的第(5)条。 事实上，引理所要求的|uv|N并不是必须的。这个限制为我们简化相应的证明提供了良好支撑扩充了的泵引理 。,2018/2/14,17,5.2 RL的封闭性,封闭性(closure property) 如果任意的、属于同一语言类的语言在某一特定运算下所得的结果仍然是该类语言，则称该语言类对此运算是封闭的有效封闭性(valid closure property)给定一个语言类的若干个语言的描述，如果存在一个算法，它可以构造出这些语言在给定运算下所获得的运算结果的相应形式的语言描述，则称此语言类对相应的运算是有效封闭的。,2018/2/14,1
9、8,5.2 RL的封闭性,定理 5-1 RL 在并、乘积、闭包运算下是封闭的。根据RE的定义，立即可以得到此定理。,2018/2/14,19,5.2 RL的封闭性,定理 5-2 RL 在补运算下是封闭的。 证明： M=(Q，q0，F) L(M)=L， 取DFA M= (Q，q0，Q-F) 显然，对于任意的x*， (q0，x)=fF (q0，x)=fQ-F 即： xL(M) xL(M)， L(M)= *-L(M)。 所以， RL 在补运算下是封闭的。定理得到证明。,2018/2/14,20,5.2 RL的封闭性,定理 5-3 RL 在交运算下封闭。证明思路,2018/2/14,21,5.2 RL
10、的封闭性,正则代换(regular substitution) 设、是两个字母表，映射,被称为是从到的代换。如果对于a，f(a)是上的 RL ，则称f为正则代换。,2018/2/14,22,5.2 RL的封闭性,先将f的定义域扩展到*上：, f()=； f(xa)=f(x)f(a)。,2018/2/14,23,5.2 RL的封闭性,再将f的定义域扩展到,对于L*,2018/2/14,24,5.2 RL的封闭性,例 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
11、(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*),2018/2/14,25,5.2 RL的封闭性,f是正则代换,则 f()=； f()=； 对于a，f(a)是上的RE； 如果r，s是上的RE，则 f(r+s)=f(r)+f(s) f(rs)=f(r)f(s) f(r*)=f(r)* 是上的RE。,2018/2/14,26,5.2 RL的封闭性,定理 5-4 设L是上的一个 RL,是正则代换，则f(L)也是 RL。证明：描述工具：RE。对r中运算符的个数n施以归纳，证
12、明f(r)是表示f(L)的RE。,2018/2/14,27,5.2 RL的封闭性,当n=0时，结论成立。当nk时定理成立,即当r中运算符的个数不大于k时：f(L(r) = L(f。 当n=k+1时，,2018/2/14,28,5.2 RL的封闭性, r=r1+r2。 f(L)=f(L(r) =f(L(r1+r2) =f(L(r1)L(r2)RE的定义 =f(L(r1)f(L(r2)正则代换的定义 =L(f(r1)L (f (r2)归纳假设 =L(f(r1)+f (r2)RE的定义 =L(f(r1+r2)RE的正则代换的定义 =L(f(r),2018/2/14,29,5.2 RL的封闭性, r=
13、r1r2。 f(L)=f(L(r) =f(L(r1r2) =f(L(r1) L(r2)RE的定义 =f(L(r1) f(L(r2)正则代换的定义 =L(f(r1) L (f (r2)归纳假设 =L(f(r1) f (r2)RE的定义 =L(f(r1r2)RE的正则代换的定义 =L(f(r),2018/2/14,30,5.2 RL的封闭性, r=r1*。 f(L)=f(L(r) =f(L(r1*) =f(L(r1)*)RE的定义 =(f(L(r1)*正则代换的定义 =(L(f(r1)*归纳假设 =L(f(r1)*)RE的定义 =L(f(r1*)RE的正则代换的定义 =L(f(r),2018/2/
14、14,31,5.2 RL的封闭性,例5-5 设=0，1，2，=a，b，正则代换f定义为： f(0)=ab； f(1)=b*a*； f(2)=a*(a+b)则： f(00)=abab； f(010)=abb*a*ab=ab+a+b；,2018/2/14,32,5.2 RL的封闭性, f(0+1+2)*)=(ab+b*a*+ a*(a+b)*=(b*a*+a*(a+b)*=(a+b)*； f(0(0+1+2)*)=ab(ab+b*a*+ a*(a+b)* =ab(a+b)*； f(012)=abb*a* a* (a+b)= ab+a*(a+b)； f(0+1)*)=(ab+ b*a* )*=(ab+b+a+ b*a* )*=(a+b)* 。,
