grammar - 无法使用上下文语法构造语言

Question

我如何用抽水引理证明这种语言(L := {ww| w ∈ {0, 1}∗}) 不能使用上下文无关文法构造？

提前致谢。

标签： grammarcontext-free-grammar

Answer 1

对上下文无关语言使用抽水引理。用于这种语言的一个很好的字符串是字符串 (0^p)(1^p)(0^p)(1^p)。抽水引理说如果语言是上下文无关的，那么这个字符串可以写成 uvxyz where |vxy| <= p, |vy| > 0 并且对于所有自然数 n，u(v^n)x(y^n)z 也在该语言中。我们有几个不同的案例：

1. vy 仅由前导 0 组成。抽这将意味着 0 的两个部分具有不同数量的 0。这行不通

2. vy 仅由前两个部分的 0 和 1 组成。这是行不通的，因为要么 0 和 1 混淆，要么前半部分的 0 和 1 比后半部分多或少。

3. vy 由第二部分的 1 组成。这与案例 1 中的原因不同。

4. vy 由第二部分的 1 和第三部分的 0 组成。这与案例 2 中的原因不同。

5. vy 由第三部分的 0 组成。这与案例 1 和 3 中的原因不同。

6. vy 由来自第三和第四部分的 0 和 1 组成。这与案例 2 和 4 中的原因不同。

7. vy 由第四部分的 1 组成。这与案例 1、3 和 5 中的原因不同。

这些都是这种情况，在任何情况下，我们都无法像我们必须的抽水引理一样抽水 (0^p)(1^p)(0^p)(1^p)。因此，我们得出结论，该语言不可能是上下文无关的。