proof - 需要证明语言 L = {a^nb^m: n < m < 2m} 不是正则的

Question

我不太了解抽水引理，可以简单分解一下如何证明这样的事情。

Answer 1

假设语言 L = {a^nb^m: n < m < 2m} 是正则的。然后，根据抽水引理，L 中长度至少为 p 的每个字符串都可以写成 xyz 其中 |xy| < p, |y| > 0 并且对于每个自然数 k，x(y^k)z 也是 L 中的一个字符串。考虑字符串 a^pb^(p+1)。这个字符串的长度至少为 p 并且在 L 中。现在我们考虑子字符串 y 的选项：

1. y 仅由 a 组成。然后，我们可以选择 k > 1 来增加 a 的数量大于 b 的数量，得到一个不在 L 中的字符串。
2. y 由 a 和 b 组成。然后，对于 k > 1，抽水会导致一些 a 出现在一些 b 之后，从而导致不可能在 L 中的字符串。
3. y 仅由 b 组成。然后，我们可以选择 k = p，因此至少有 2p + 1 个 b，b 的数量是 a 的两倍多，因此字符串不在 L 中。

因为这三种方式是选择子串 y 的唯一方式，所以没有办法选择 y 使得泵引理的条件得到满足。这是一个矛盾。因此，语言是规则的假设一定是不正确的。由此可见，语言不规则。证明是通过矛盾/减少和荒谬的。