证明 L = {a^n b^m | n>=m} 是不规则语言
proof L = {a^n b^m | n>=m} is irregular language
我一直在为抽取引理寻找 S。有什么想法可以证明
L = {a^n b^m | n>=m}是不规则语言？
抽取引理指出：
If L is a regular language, then there exists a natural number p such that any string w of length at least p can be written as w = uvx where |uv| <= p, |v| > 0 and for all natural numbers n, u(v^n)x is also in the language.
为了使用抽取引理证明一种语言不是正则的，我们需要设计一个字符串 w 使得语句的其余部分失败：也就是说，没有有效的 u、v 和 x 赋值。
我们的语言 L 要求 a 的数量与 b 的数量相同。满足字符串 w 的长度至少为 p 的假设的最短字符串是 a^(p/2) b^(p/2)。我们可以猜测这是我们的字符串。如果我们这样做，我们有几种情况：
- v 完全由 a 组成。但是，抽取将导致 a 和 b 的数量不同，因此生成的字符串不在语言中；矛盾。
- v 跨越 a 和 b。但是，泵送将导致 a 和 b 在中间混淆，而我们的语言要求所有 a 都在前面。这也是一个矛盾。
- v 完全由 b 组成。但是，我们遇到了与案例 #1 相同的矛盾。
在所有情况下，w 的这种选择都导致了矛盾。这意味着猜测成功了。
这里w有一个更简单的选择：选择w = a^p b^p，那么只有一种情况。但我们的选择很好。如果我们的选择没有成功，我们可以从那个选择中了解到哪里出了问题，然后选择另一个候选人。
我一直在为抽取引理寻找 S。有什么想法可以证明 L = {a^n b^m | n>=m}是不规则语言？
抽取引理指出：
If L is a regular language, then there exists a natural number p such that any string w of length at least p can be written as w = uvx where |uv| <= p, |v| > 0 and for all natural numbers n, u(v^n)x is also in the language.
为了使用抽取引理证明一种语言不是正则的，我们需要设计一个字符串 w 使得语句的其余部分失败：也就是说，没有有效的 u、v 和 x 赋值。
我们的语言 L 要求 a 的数量与 b 的数量相同。满足字符串 w 的长度至少为 p 的假设的最短字符串是 a^(p/2) b^(p/2)。我们可以猜测这是我们的字符串。如果我们这样做，我们有几种情况：
- v 完全由 a 组成。但是，抽取将导致 a 和 b 的数量不同，因此生成的字符串不在语言中；矛盾。
- v 跨越 a 和 b。但是，泵送将导致 a 和 b 在中间混淆，而我们的语言要求所有 a 都在前面。这也是一个矛盾。
- v 完全由 b 组成。但是，我们遇到了与案例 #1 相同的矛盾。
在所有情况下，w 的这种选择都导致了矛盾。这意味着猜测成功了。
这里w有一个更简单的选择：选择w = a^p b^p，那么只有一种情况。但我们的选择很好。如果我们的选择没有成功，我们可以从那个选择中了解到哪里出了问题，然后选择另一个候选人。