形式陈述

若 $L$$L$ 是正则语言，则存在泵长 $p\ge1$$p\ge 1$，使每个满足 $w\in L$$w\in L$ 且 $|w|\ge p$$|w|\ge p$ 的字符串都可分解为

$$ w=xyz $$$$w=xyz$$

并满足

$$ |xy|\le p,\qquad |y|>0,\qquad \forall i\ge0, \quad xy^iz\in L. $$$$|xy|\le p,|y|>0,\mathrm{\forall }i\ge 0,x{y}^{i}z\in L.$$

分解 $x,y,z$$x,y,z$ 可以依赖于 $w$$w$，但在选定后必须对所有 $i\ge0$$i\ge 0$ 同时成立。

直觉

有限自动机读入足够长前缀时必重复某个状态，重复段形成环。绕该环零次、一次或多次都回到同一状态，因此后缀接受行为不变。

例子与边界

要证明 $\{0^n1^n:n\ge0\}$$\{0^n{1}^n:n\ge 0\}$ 非正则，可对任意候选 $p$$p$ 取 $w=0^p1^p$$w=0^p{1}^p$；任意满足 $|xy|\le p$$|xy|\le p$ 的非空 $y$$y$ 只含 $0$$0$，泵送后打破数量相等。量词顺序是“对所有 $p$$p$ 选 $w$$w$，对所有合法分解选某个 $i$$i$ 使失败”。满足泵性质是正则性的必要条件，不是充分条件。

推论与应用

泵引理是证明语言非正则的经典工具。它不能用于证明语言正则，也并非对所有非正则语言都容易使用；Myhill–Nerode 定理常给出更强、更结构化的判别。

参考资料

• John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006，§4.1。
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，§1.4。