1

问:证明 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 不是上下文无关的


我的证明正确吗?

4

1 回答 1

0

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

设 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 与接受上下文无关语言的下推自动机中的状态数密切相关)。

于 2018-11-12T14:23:03.973 回答