是否正确使用泵引理？

Question

我试图通过 Pumping Lemma 证明以下语言不是正则的。但我不确定我是否做得正确。

{L = a ^{2 n} | n>= 0 }

到目前为止，我所做的如下：

s = a ^{2 p}

x = a ^{2 i}

y = a ^{2 j}

z = a ^{2 p-ij}

因此 xy ² z = a ^{2 p+j}

这意味着 a ^{2 p+j} > a ^{2 p} ，使语言不规则

我做得对吗？还是我有什么问题？

Answer 1

不完全是，你得出了正确的结论，但推理有点偏离。所述泵送引理状态，对于每一个正则语言L，存在一个整数p >= 1，每一个字符串s长度大于或等于对p可写为s = xyz以下的条件成立，其中：

1. y 非空
2. xy≤p的长度
3. xy ⁱ z 在L所有 i ≥ 0的语言中

你的第一步是正确的，s = a ^{2 p}确实比 p 长。然而，抽运引理指出 s 可以被划分为s = xyz满足上述条件。换句话说，s存在一个除法 as s = xyz，但是你不能选择那个除法是什么，除了知道它应该满足上述三个属性。

在您的情况下L，语言只由 a 组成，其中 a 的数量是 2 的幂。现在取 s = a ^{2 p}，我们知道下一个最长的字符串L是 (a ^{2 p} ) ²。从那里，如果前两个条件成立，可以看出第三个条件肯定不成立i = 2，因为 a ^{2 p} < xy ² z < (a ^{2 p} ) ²。（在简单的英语中，xy ² z的长度介于^{2 的}幂之间，因此它不在该语言中，L因为它是常规语言时会出现的情况）