泵引理表明`{a^n b^m | n=km for k in N}` 不规则
Pumping lemma to show that `{a^n b^m | n=km for k in N}` is not regular
我应该如何证明 L={a^n b^m | n=km for k in N} 不是使用泵引理的常规语言？
我从 L、w=a^n b^m 和 n=km 中的 k 中的 N 开始。
w有三种可能的分解：
a^i * a^j * a^(n-i-j) b^ma^i * a^(n-i) b^j * b^(m-j)a^n b^i * b^j * b^(m-i-j)
pumping point 2)的中间部分会导致混淆词，这显然不是L，但我不明白为什么1)不能给你一个很好的分解:
假设您泵 a^j x 次。那么新单词中a的数量将是i+xj+n-i-j = n+(x-1)j。我们知道 n=km 有一些 m。我们必须证明存在 x 使得新词不在 L 中。但是让我们假设 j=m（这当然是可能的，因为 n=km 总是有足够数量的 a，除非 k=0，但我们得到一个微不足道的情况）。然后是 n+(x-1)j = km+(x-1)m = m(n+x-1)，对于所有 x，其形式为 {a^n b^m | n=km for k in N}。因此，对于每个 w，我们都有一个分解 uvz，这样 u v^i z 对于所有 i 都在 L 中。因此，根据泵引理，L 是规则的。
我错过了什么？
编辑：给定的 Pumping 引理公式：
Let L be a regular language accepted by a DFA with k states. Let w be any word in L with length >= k. Then w can be written as u v z with |uv| <=k, v>0 and u v^i z in L for all i>=0
证明这一点的一个可能更简单的方法是首先修改语言。
因为正则语言在补语和与另一个正则表达式的交集下封闭。
这意味着你可以通过证明complement(L)不是常规语言来证明L不是常规语言，因为如果L'是常规语言，L 是，反之亦然。交叉路口也是如此。
足以证明L'也不是正则的：
L' = intersection(complement(L),a*b*})
因此
L'={a^nb^m|n != k*m, for any k in N}
那么证明就变得更容易了，因为你可以显示任何你用作抽取引理的部分，如果它有长度 l，你可以抽取足够的次数来达到倍数。
我应该如何证明 L={a^n b^m | n=km for k in N} 不是使用泵引理的常规语言？
我从 L、w=a^n b^m 和 n=km 中的 k 中的 N 开始。
w有三种可能的分解：
a^i * a^j * a^(n-i-j) b^ma^i * a^(n-i) b^j * b^(m-j)a^n b^i * b^j * b^(m-i-j)
pumping point 2)的中间部分会导致混淆词，这显然不是L，但我不明白为什么1)不能给你一个很好的分解:
假设您泵 a^j x 次。那么新单词中a的数量将是i+xj+n-i-j = n+(x-1)j。我们知道 n=km 有一些 m。我们必须证明存在 x 使得新词不在 L 中。但是让我们假设 j=m（这当然是可能的，因为 n=km 总是有足够数量的 a，除非 k=0，但我们得到一个微不足道的情况）。然后是 n+(x-1)j = km+(x-1)m = m(n+x-1)，对于所有 x，其形式为 {a^n b^m | n=km for k in N}。因此，对于每个 w，我们都有一个分解 uvz，这样 u v^i z 对于所有 i 都在 L 中。因此，根据泵引理，L 是规则的。
我错过了什么？
编辑：给定的 Pumping 引理公式：
Let
Lbe a regular language accepted by a DFA withkstates. Letwbe any word inLwith length>= k. Thenwcan be written asu v zwith|uv| <=k,v>0andu v^i zinLfor alli>=0
证明这一点的一个可能更简单的方法是首先修改语言。
因为正则语言在补语和与另一个正则表达式的交集下封闭。
这意味着你可以通过证明complement(L)不是常规语言来证明L不是常规语言，因为如果L'是常规语言，L 是，反之亦然。交叉路口也是如此。
足以证明L'也不是正则的：
L' = intersection(complement(L),a*b*})
因此
L'={a^nb^m|n != k*m, for any k in N}
那么证明就变得更容易了，因为你可以显示任何你用作抽取引理的部分，如果它有长度 l，你可以抽取足够的次数来达到倍数。