证明L = {a ^ n b ^ m | n> = m}是不规则语言

Question

我被困在寻找S来抽引引理。有什么想法可以证明L = {a ^ n b ^ m | n> = m}是不规则的语言吗？

Answer 1

抽水引理说：

如果L是常规语言，则存在自然数p，使得长度至少为p的任何字符串w都可以写成w = uvx，其中| uv | <= p，| v | > 0，并且对于所有自然数n，u（v ^ n）x也是该语言。

为了证明使用抽运引理的语言不是正常的，我们需要设计一个字符串w，以使语句的其余部分失败：也就是说，没有u，v和x的有效分配。

我们的语言L要求a的数量必须与b的数量相同。满足字符串w的长度至少为p的假设的最短字符串为a ^（p / 2）b ^（p / 2）。我们可以将其作为字符串。如果这样做，我们有几种情况：

1. v完全由a组成。但是然后，泵送将导致a和b的数目不同，因此结果字符串不是语言中的；矛盾。
2. v跨越a和b。但是然后，抽水将导致a和b在中间混合在一起，而我们的语言要求所有a都首先出现。这也是一个矛盾。
3. v完全由b组成。但是然后，我们与情况＃1有相同的矛盾。

在所有情况下，w的选择都导致了矛盾。这意味着猜测有效。

这里w有一个更简单的选择：选择w = a ^ p b ^ p，那么只有一种情况。但是我们的选择效果很好。如果我们的选择没有解决，我们可以从该选择中学到出了什么问题并选择了其他候选人。