正则语言泵引理

有限自动机面对足够长的接受字，必定在输入尚未读完时重访某个状态。两次访问之间的输入片段对控制状态的净效果为零：从该状态出发，读完片段又回来。机器看不出这段究竟出现一次、零次还是更多次，于是整个语言必须容忍某种局部重复。

泵长度并不是语言中所有周期的最小值，也不是输入被平均切成的块长。证明只告诉我们，若有一台 $p$ 状态 DFA，那么每个足够长的接受运行在前 $p$ 个字符内含环。不同的字可以选择不同位置的环，同一个字也可能有多种合法分解。

使用引理证明非正则性像一场量词游戏：先假设对手给出任意泵长度 $p$；你据此选择一个结构脆弱的长字 $w$；对手再选择任何合法分解；你必须针对这份分解找到某个泵次数破坏成员资格。若自己先挑 $y$，就交换了量词，证明不成立。

证明

不正则。假设引理给出泵长度 $p$，选择 $w=0^p{1}^p$。对任意满足 $w=xyz$、$|xy|\le p$、$|y|>0$ 的分解，中段 $y$ 完全落在第一段 0 中，故 $y=0^k$，其中 $k\ge 1$。取 $i=0$ 后，

与所有 $i$ 都应留在 $L$ 矛盾。选择 $0^p{1}^p$ 是为了利用长度约束，把任意合法环都限制在同一种符号内；删环随即打破两段相等关系。

上述反证的逻辑否定应完整写为

只击败一种分解，或只为预先选定的 $p$ 给出反例，都没有否定泵引理。

泵引理是正则性的必要条件，不是充分条件。成功为某些字找到可泵片段，最多说明这些字没有暴露矛盾；它既没有构造有限自动机，也没有覆盖定理要求的全部量词。有限语言则因没有足够长的成员而真空满足引理，并且本来就正则。

长度约束 $|xy|\le p$ 把环限制在运行的早期，使证明者可以设计一个前缀结构单一的见证字。若只要求某处存在环，分解可能跨过决定成员资格的结构边界，许多标准反证便无法控制中段。

泵引理把“有限状态必有环”转化为可操作的非正则性证明。它特别适合计数匹配、长距离依赖和复制结构中能用短前缀锁定环位置的语言；若目标语言形状复杂，可先利用闭包与正则过滤器提取一个简单核心，再应用引理。

Myhill–Nerode 定理公理库Myhill–Nerode 定理Myhill–Nerode theorem语言正则当且仅当前缀的不同未来行为只有有限种，其类数恰为最小 DFA 状态数。提供与本引理互补的路线：构造无限多个两两可区分前缀即可证明非正则，还能给出有限情形的精确状态下界。泵引理通常从一条长接受运行找环，Myhill–Nerode 则从许多前缀的不同未来找下界；前者只是必要条件，后者是充要刻画。