computer-science - 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 可以划分为 uv^ixy^iz

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（不满足第 3 个条件）

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

因此 L 不是上下文无关的

---

我的证明正确吗？

Answer 1

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

设 P=2, S= 00 11 00 11

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

下一个错误是这样的：

S 可分为 uv^ixy^iz […]

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

你绝对是在正确的轨道上：

字符串 = 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 以限制有趣案例的数量（因为 |vxy| < P，v 和 y 只能由来自相邻部分的符号组成）。我们从来没有说过 P 是什么数字。事实上，如果语言是上下文无关的，则只有 P 的值（那么，P 与接受上下文无关语言的下推自动机中的状态数密切相关）。