最近我在读Michael Sipser的《Introduction to the Theory of Computation 3rd Edition》，里面讲到了泵引理这个核心命题——也就是定理1.70：

定理1.70（泵引理）
如果$A$是正则语言，那么存在一个数$p$（泵长度），使得对于$A$中任意长度不小于$p$的字符串$s$，都可以将$s$拆分为三个部分$s=xyz$，满足以下条件：

• 对于任意$i\geq 0$，$xy^iz\in A$；
• $|y|>0$；
• $|xy|\leq p$。

在这本书里，作者总用泵引理来证明某个语言不是正则的。比如例1.74中，他就用泵引理证明了语言$C={w\mid w\text{ 包含数量相等的0和1}}$不是正则的，具体证明过程是这样的：

例1.74的证明过程
假设$C$是正则的，设$p$为泵引理给出的泵长度。取字符串$s=0^p1p$，它属于$C$且长度大于$p$，根据泵引理，$s$可以拆分为$xyz$，且对任意$i\geq0$，$xy^iz$都属于$C$。

一开始看起来好像能找到合法拆分——比如让$x$和$z$为空串，$y=0^p1p$，这样$xy^iz$永远有相等数量的0和1，确实属于$C$。但泵引理的第三个条件派上了用场：它要求$|xy|\leq p$，这意味着$y$只能由0组成。这样一来，当我们取$i=2$时，$xyyz$的0数量会远多于1，显然不属于$C$，这就产生了矛盾，所以$C$不是正则的。

这里选$s$的时候得格外小心，如果选$s=(01)^{p$就会出问题——哪怕考虑第三个条件，这个字符串也能被“泵”：比如设$x=\epsilon$，$y=01$，$z=(01)}{p-1}$，这样$xy^iz$永远满足0和1数量相等，属于$C$。要是第一次选的字符串不对，换一个就行。

不过我发现，就算不知道泵引理，也能轻松证明$C$不是正则的，核心就是鸽巢原理——作者的方法感觉太教条了。

我的思路是这样的：假设存在一个识别$C$的DFA$M$，给$M$输入一串足够长的0（比如$0^{k$，$k$足够大）。因为$M$的状态是有限的，根据鸽巢原理，在处理这串0的过程中，$M$一定会进入某个循环状态。然后我们输入$0}k1^{k$（这属于$C$），那如果我们在循环部分多“泵”几次0，得到的字符串比如$0}{k+m}1^k$（$m>0$），这个字符串的0数量明显比1多，却应该被$M$接受，但它不属于$C$，这就产生了矛盾。

这就让我开始思考：泵引理真的有用吗？有没有那种不用泵引理就很难证明其非正则性的问题？我甚至怀疑泵引理是不是一个不值得专门命名的命题。

备注：内容来源于stack exchange，提问作者tchappy ha