上下文无关语言（泵引理 a^n b^m c^min(n,m)）

Question

我正在努力解决以下问题。我应该使用泵引理。

证明{a^n b^m c^min(n,m) | m,n >= 0 } 不是上下文无关的。

Answer 1

考虑语言中的字符串 a^p b^p c^p。通过上下文无关语言的泵引理，这个字符串可以写成 uvxyz 这样：

• |vxy|
• |维| > 0
• u(v^n)x(y^n)z 也是所有自然数 n
的语言

在我们的字符串中放置 vxy 有五种情况需要考虑：

1. vxy完全是第一段a的而已。如果我们选择 n = 0 并抽空，我们将丢失 a，但随后也需要减少 c 的数量以保留在语言中。 vxy 的这种放置不起作用。

2. vxy 跨越 a 和 b。选择 n = 0 并抽空将丢失 a 和 b。由于 c 的数量没有相应减少，因此 vxy 的这个选择也不起作用。

3. vxy完全在b的那一段而已。案例 1 中的相同论点也适用于此。

4. vxy 跨越 a 和 c。选择 n > 0 并向上抽水将添加 b 和 c。现在c的个数将严格大于a的个数，也就是说这个选择也不行。

5. vxy完全在c的那段而已。向任一方向泵送都会使 c 的数量与 a 的数量和 b 的数量不同，因此选择也会失败。

有五个可能的位置可以将 vxy 放入我们的字符串中，但都失败了。这意味着我们的字符串不能根据泵引理的要求来编写，因此，我们的语言不能是上下文无关的。