CFL 的泵送引理

Question

问： 证明 L={ww|w ∈ {0,1}*} 不是上下文无关的

我的解决方案：

假设 L 是上下文无关的

设其抽气长度为P

因此，

字符串 = 0^P 1^P 0^P 1^P

令P=2， S= 00 11 00 11

S 可以除以 u v^i x y^i z

0 0 110 0 11
u v  x  y  z

吸完后，

0 00 110 00 11
u  v  x   y  z

0^3 1^2 0^3 1^2 因此它的形式为ww（满足第一个条件）

|vy|=4>0 （满足第二个条件）

|vxy|= 7 大于泵浦长度 2 （不满足第三个条件）

因此，与 L 是上下文无关的假设相矛盾。

因此 L 不是上下文无关的

---

我的证明正确吗？

Answer 1

这个证明是不正确的。出轨的地方就在这里：

令 P=2，S= 00 11 00 11

你不能“让”P 成为任何东西。由于上下文无关语言的泵引理，P 被假设存在，但它仍然是一个假设的数字。即使证明的其余部分是正确的，您所要证明的只是数字 P=2 不起作用。你需要证明 P 没有选择，才能证明该语言不是上下文无关的。

下一个错误是这样的：

S 可以除以 u v^i x y^i z […]

确实，S 可以按照你的建议进行划分。但是，它也可以以其他方式划分。请注意，上下文无关语言的泵引理仅要求 |vxy| < P and |vy| > 0。特别是，u、v、x、y 和 z 中的任何一个都可以是空字符串，只要 v 和 y 都不为空即可。

您绝对走在正确的道路上：

字符串 = 0^P 1^P 0^P 1^P

从这里开始，不要选择特定的 P 或特定的作业，而是从整体上考虑有趣的作业类型或案例；有趣的不同案例的数量实际上很小。

1. v 和 y 仅由字符串第一部分中的 0 组成。泵浦导致第一部分中 0 的数量与接下来的三个部分不匹配。
2. v 和 y 仅由字符串第一部分和第二部分的 0 和 1 组成。泵送会导致字符串第一和第二部分中的 0 和/或 1 数量与第三和第四部分不匹配。
3. v 和 y 仅由字符串第二部分中的 1 组成。与(1)基本相同
4. v 和 y 由字符串第二部分和第三部分的 1 和 0 组成。与(2)基本相同
5. v 和 y 由字符串第三部分的 0 组成。与(1)和(3)基本相同
6. v 和 y 由字符串第三和第四部分的 0 和 1 组成。与(2)和(4)基本相同
7. v 和 y 由字符串第四部分的 1 组成。与(1)、(3)、(5)基本相同。

这些情况涵盖了 v 和 y 的所有可能的分配，并且它们都不能像引理所说的那样被抽运。这就是矛盾所在。关键是使用 |vxy| < P to limit the number of interesting cases (because |vxy| < P, v and y can consist of symbols only from adjacent sections). We never said what number P was; in fact, there is only a value for P if the language is context-free (then, P is closely related to the number of states in a pushdown automaton which accepts the context-free language).