上午正确使用泵引理？(Am using the pumping lemma correctly?)

我试图证明下列语言不是通过泵引理经常。 但我真的不知道我是否已经正确的。

N> = 0}

我到目前为止已经做的是以下几点：

其中^p = ²和

X = A ^{2 I}

且^j = ²

Z = ^{2 PIJ}

因而的xy ² Z =一个^{2个P + J}

这意味着^{2个P + J> 2 P，}使得语言不是正则的

我在做正确吗？ 或者是有什么我错了吗？

Answer 1:

不完全是，你得出正确的结论，但推理是有点过。 所述抽水引理指出，对于每一个正则语言L ，存在一个整数p >= 1 ，其中每一个串s长度大于或等于p可写为s = xyz位置在以下条件成立：

1. y非空
2. XY≤P的长度
3. XY ^I Z是在语言L对于所有的i≥0

第一步是正确的，S = ^{2 p}是确实长于页。 然而，泵引理指出S可为被划分s = xyz满足上述条件。 换句话说， 存在作为S的划分s = xyz ，但你不要选择该部门是什么，除了知道它应该满足上述三个特性。

在你的情况L是由语言只是一个就是其中的数量是2。现在服用S = ^{2 P} A的功率，我们知道，在未来的最长的字符串L是^{（2 P）2。} 从那里，如果前两个条件成立，可以看出，第三个条件肯定不能保持i = 2 ，因为^{2 P} <XY ² Z ^{<（2 P）2。} （在普通的英语，XY ² z的长度为二的幂之间，所以它不是在语言L如它本来，如果它是一个正则语言）

文章来源: Am using the pumping lemma correctly?