形式陈述

若 $L$$L$ 是上下文无关语言，则存在泵长度 $p$$p$，使每个满足 $|w|\ge p$$|w|\ge p$ 的 $w\in L$$w\in L$ 都可分解为

$$ w=uvxyz, $$$$w=uvxyz,$$

并满足 $|vxy|\le p$$|vxy|\le p$、$|vy|>0$$|vy|>0$，以及对所有 $i\ge0$$i\ge 0$，

$$ uv^ixy^iz\in L. $$$$u{v}^{i}x{y}^{i}z\in L.$$

证明在足够高的语法树根到叶路径上重复一个非终结符，再同步复制或删除其两层之间的两个产出片段。分解可依赖于 $w$$w$，而反证时必须对所有合法分解都构造失败的泵指数。

直觉

有限个非终结符无法为任意深的推导树提供全新标签，所以某个递归结构必重复；重复的上下文在字符串的两个位置同时留下可泵送痕迹。

例子与边界

语言 $\{a^nb^nc^n:n\ge0\}$$\{a^n{b}^n{c}^n:n\ge 0\}$ 不是 CFL：取 $a^pb^pc^p$$a^p{b}^p{c}^p$，因 $|vxy|\le p$$|vxy|\le p$，两个被泵片段不可能同时覆盖三段，泵后至少有一种计数失衡。量词顺序很关键：证明者先选 $p$$p$，反证者选长词，随后必须应对证明者给出的任意分解。泵引理只是必要条件；某些非 CFL 也满足类似泵性质，不能据此证明一个语言是 CFL。

推论与应用

泵引理是排除候选 CFG/PDA 的常用工具；当局部窗口难以控制时，可改用 Ogden 引理或闭包性质。它还解释了单栈结构能够复制局部嵌套，却难以同步维护三个独立计数。

参考资料

• John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006，Ch. 7, pumping lemma for context-free languages。
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，Ch. 2, pumping lemma for context-free languages。