regular-language - 上下文无关语言（抽取引理 a^nb^mc^min(n,m)）

Question

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

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

Answer 1

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

• |vxy| < p
• |维| > 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 放入我们的字符串中，但都失败了。这意味着我们的字符串不能根据泵引理的要求编写，因此，我们的语言不能是上下文无关的。