如何证明语言{(a^m)(b^n)(c^k): m≠k且m,n,k∈N}是非正则语言？

用反证法结合正则语言的泵引理来证：

1. 先假设L是正则的，那根据泵引理，存在一个泵长度p，只要是L里长度≥p的字符串s，都能拆成x y z三个部分，满足：

   • |xy| ≤ p（前p个字符里包含xy）
   • |y| ≥ 1（y不能为空）
   • 不管i取非负整数多少，xy^i z都还在L里

2. 构造字符串s = a^p c^{p+1}，这个字符串肯定在L里——因为m=p，k=p+1，m≠k，n=0也是自然数，而且s的长度是2p+1，明显≥p，符合泵引理的前提。

3. 因为|xy| ≤ p，所以xy只能落在s开头的a段里，也就是x是若干个a，y也是若干个a（至少1个），剩下的z就是剩下的a加上后面的c^{p+1}。具体来说：

   • 设x = a^t（t≥0，t < p）
   • y = a^s（s≥1，t+s ≤ p）
   • z = a^{p-t-s} c^{p+1}

4. 现在取i=2，把y泵一次，得到xy^2 z：
   计算一下这个字符串的组成：a^t * a^{2s} * a^{p-t-s} c^{p+1} = a^{p+s} c^{p+1}。因为s≥1，这里最极端的情况是s=1，那这个字符串就变成a^{p+1} c^{p+1}——这时候m=p+1，k=p+1，m=k，显然这个字符串不在L里。

5. 但根据泵引理，如果L是正则的，xy^2 z必须属于L，这就矛盾了。所以之前的假设不成立，L是非正则语言。

另外也可以换个构造字符串的思路，比如用s = a^{p+1} b^p c^p，泵i=0的时候得到a^p b^p c^p，这个字符串m=k=p，同样不在L里，也能导出矛盾。

内容的提问来源于stack exchange，提问作者李力扬