context-free-grammar - 是否正确使用了泵引理？

Question

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

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

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

s = a ^{2 p}

x = 一个^2我

y = a ^{2 j}

z = a ^{2 p-ij}

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

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

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

Answer 1

不完全是，你得出了正确的结论，但推理有点不对劲。Pumping 引理指出，对于每种常规语言，都L存在一个整数，其中每个长度大于或等于的p >= 1字符串都可以写成满足以下条件：sps = 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像普通语言那样的语言）