证明语言不是上下文无关的？
Prove the language is not context-free?
你如何证明下面给出的语言L不是上下文无关的，我想知道我下面给出的证明是否有意义，如果没有，正确的证明方法是什么？
L = {a^n b^n c^i|n ≤ i ≤ 2n}
我试图通过矛盾来解决这种语言。假设 L 是规则的并且具有泵浦长度 p，使得 S = a^p b^p c^p。观察到 S ∉ L。由于必须有一个长度小于 p 的泵循环 xy，这可以复制由一些 b 组成的 y 导致 x(y^2)z 进入语言，因为 b 的数量超过c 的数量不再受 i 的给定条件 n ≤ i ≥ 2n 的约束，因此，我们有矛盾，因此语言 L 不是上下文无关的。
反证法。假设语言是上下文无关的。然后，通过上下文无关语言的泵引理，L 中的任何字符串都可以写为 uvxyz，其中 |vxy| < p, |维| > 0 并且对于所有自然数 k，u(v^k)x(y^k)z 也在该语言中。选择a^p b^p c^(p+1)。然后我们必须能够将这个字符串写成 uvxyz 以便 |vy| > 0。有几种可能性需要考虑：
- v 和 y 仅由 a 组成。在这种情况下，向任一方向泵送都会导致 a 和 b 的数字不同，从而产生一个不是该语言的字符串；所以这不可能。
- v 和 y 仅由 a 和 b 组成。在这种情况下，pumping 可能会使 a 和 b 的数量保持相同，但 pumping up 最终会导致 c 的数量小于 a 和 b 的数量；所以这不可能。
- v 和 y 仅由 b 组成。这种情况与上面的 (1) 类似，因此不能作为有效选择。
- v 和 y 仅由 b 和 c 组成。也类似于 (1) 和 (3)，因为泵送会导致 a 和 b 的数量不同。
- v 和 y 仅由 c 组成。抽气最终会导致 c 的数量超过 a 的两倍；所以这也不可能是这种情况。
无论我们如何选择 v 和 y，抽取都会产生非该语言的字符串。这是一个矛盾；这意味着我们假设该语言是上下文无关的一定是不正确的。
你如何证明下面给出的语言L不是上下文无关的，我想知道我下面给出的证明是否有意义，如果没有，正确的证明方法是什么？
L = {a^n b^n c^i|n ≤ i ≤ 2n}
我试图通过矛盾来解决这种语言。假设 L 是规则的并且具有泵浦长度 p，使得 S = a^p b^p c^p。观察到 S ∉ L。由于必须有一个长度小于 p 的泵循环 xy，这可以复制由一些 b 组成的 y 导致 x(y^2)z 进入语言，因为 b 的数量超过c 的数量不再受 i 的给定条件 n ≤ i ≥ 2n 的约束，因此，我们有矛盾，因此语言 L 不是上下文无关的。
反证法。假设语言是上下文无关的。然后，通过上下文无关语言的泵引理，L 中的任何字符串都可以写为 uvxyz，其中 |vxy| < p, |维| > 0 并且对于所有自然数 k，u(v^k)x(y^k)z 也在该语言中。选择a^p b^p c^(p+1)。然后我们必须能够将这个字符串写成 uvxyz 以便 |vy| > 0。有几种可能性需要考虑：
- v 和 y 仅由 a 组成。在这种情况下，向任一方向泵送都会导致 a 和 b 的数字不同，从而产生一个不是该语言的字符串；所以这不可能。
- v 和 y 仅由 a 和 b 组成。在这种情况下，pumping 可能会使 a 和 b 的数量保持相同，但 pumping up 最终会导致 c 的数量小于 a 和 b 的数量；所以这不可能。
- v 和 y 仅由 b 组成。这种情况与上面的 (1) 类似，因此不能作为有效选择。
- v 和 y 仅由 b 和 c 组成。也类似于 (1) 和 (3)，因为泵送会导致 a 和 b 的数量不同。
- v 和 y 仅由 c 组成。抽气最终会导致 c 的数量超过 a 的两倍；所以这也不可能是这种情况。
无论我们如何选择 v 和 y，抽取都会产生非该语言的字符串。这是一个矛盾；这意味着我们假设该语言是上下文无关的一定是不正确的。