这个证明是不正确的。它出轨的地方在这里:
设 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 或特定的分配,而是将有趣的分配类型或案例作为一个整体来考虑;有趣的不同案例的数量实际上很少。
- v 和 y 仅由字符串第一部分的 0 组成。抽水会导致第一部分中的 0 数量与接下来的三个部分不匹配。
- v 和 y 仅由字符串第一和第二部分的 0 和 1 组成。抽吸会导致弦的第一和第二部分的 0 和/或 1 的数量与第三和第四部分不匹配。
- v 和 y 仅由字符串第二部分的 1 组成。与(1)基本相同
- v 和 y 由字符串第二和第三部分的 1 和 0 组成。与(2)基本相同
- v 和 y 由字符串第三部分的 0 组成。与(1)和(3)基本相同
- v 和 y 由字符串第三和第四部分的 0 和 1 组成。与(2)和(4)基本相同
- v 和 y 由字符串第四部分的 1 组成。与(1)、(3)、(5)基本相同。
这些情况涵盖了 v 和 y 的所有可能分配,并且没有一个可以像引理所说的那样被抽出。这就是矛盾。关键是使用 |vxy| < P 以限制有趣案例的数量(因为 |vxy| < P,v 和 y 只能由来自相邻部分的符号组成)。我们从来没有说过 P 是什么数字。事实上,如果语言是上下文无关的,则只有 P 的值(那么,P 与接受上下文无关语言的下推自动机中的状态数密切相关)。