自动机与形式语言_第五章_泵引理汇编.pptxVIP

;;;;;;;;Example: Testing Membership;Example: Testing Membership;Example: Testing Membership;Example: Testing Membership;Example: Testing Membership;Example: Testing Membership;;定理 5-13 设L是字母表∑上的 RL ，对任意x∈∑*，存在判定x是不是L的句子的算法。 从一定的意义上讲，接受L的DFA M就是判定x是否L的一个句子的“算法”。 ;;;定理 5-10 设DFA M=(Q，∑，δ，q0，F)，L=L(M)非空的充分必要条件是：存在x∈∑*，|x||Q|，δ(q0，x)∈F。 证明：充分性显然。 必要性：M的状态转移图中必存在一条从q0到某一个终止状态qf且无重复状态的路，此路中的状态数n≤|Q|。此路的标记x满足|x|≤n-1。而δ(q0，x)∈F。即x是L=L(M)的长度小于|Q|的句子。 ;;;22;;;;26;5.1 RL的泵引理 ;5.1 RL的泵引理;5.1 RL的泵引理 ; M=(Q，∑，δ，q0，F) |Q|=N z= a1a2…am m≥N δ(q0，a1a2…ah)=qh 状态序列q0，q1，…，qN中，至少有两个状态是相同：qk=qj ;δ(q0，a1a2…ak)=qk δ(qk，ak+1…aj)=qj=qk δ(qj，aj+1…am)=qm 对于任意的整数i≥0 δ(qk，(ak+1…aj)i) =δ(qk，(ak+1…aj)i-1) … =δ(qk，ak+1…aj)=qk ;故， δ(q0，a1a2…ak(ak+1…aj)i aj+1…am)=qm 也就是说， a1a2…ak(ak+1…aj)i aj+1…am∈L(M) u= a1a2…ak， v=ak+1…aj， w= aj+1…am uviw∈L ;例 5-1 证明{0n1n|n≥1}不是 RL。 证明： 假设L={0n1n|n≥1} 是 RL z=0N1N 按照泵引理所述 v=0k k≥1 此时有， u=0N-k-j w=0j1N ;从而有， uviw=0N-k-j(0k)i0j1N=0N+(i-1)k1N 当i=2时，我们有： uv2w=0N+(2-1)k1N = 0N+k1N 注意到k≥1，所以， N+kN。 这就是说， 0N+k1N?L 这与泵引理矛盾。所以，L不是 RL。 ;例 5-2 证明{0n|n为素数}不是 RL。 证明：假设L={0n|n为素数} 是 RL。 取 z=0N+p ∈L ， 不妨设v=0k， k≥1 从而有， uviw=0N+p-k-j(0k)i0j =0N+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时， uvN+p+1w=0(N+p)(1+k) ?L 这与泵引理矛盾。所以，L不是 RL。 ;例 5-3 证明{0n1m2n+m|m，n≥1}不是 RL。 证明：假设L={0n1m2n+m|m，n≥1} 是 RL。 取z=0N1N22N 设 v=0k k≥1 从而有， uviw=0N-k-j(0k)i0j1N22N =0N+(i-1)k1N22N; uv0w=0N+(0-1)k1N22N = 0N-k1N22N 注意到k≥1， N-k+N=2N-k2N 0N-k1N22N ?L 这个结论与泵引理矛盾。所以，L不是 RL。 ;用来证明一个语言不是 RL 不能用泵引理去证明一个语言是 RL。 ⑴ 由于泵引理给出的是 RL 的必要条件，所以，在用它证明一个语言不是 RL 时，我们使用反证法。 ⑵ 泵引理说的是对 RL 都成立的条件，而我们是要用它证明给定语言不是 RL ，这就是说，相应语言的“仅仅依赖于L的正整数N”实际上是不存在的。所以，我们一定是无法给出一个具体的数的。因此，人们往往就用符号N来表示这个“假定存在”、而实际并不存在的数。 ;⑶ 由于泵引理指出，如果L是 RL ，则对任意的z∈L，只要|z|≥N，一定会存在u、v、w，使uviw∈L对所有的i成立。因此，我们在选择z时，就需要注意到论证时的简洁和方便。 ⑷ 当一个特意被选来用作“发现矛盾”的z确定以后，就必须依照|uv|≤N和|v|≥1的要求，说明v不存在(对“存在u、v、w”的否定) 。;⑸ 与选z时类似，在寻找i时，我们