上下文无关语言泵引理

有限个非终结符无法为任意深的解析树提供全新标签，所以树足够高时，某条根到叶路径必会重复非终结符。两次出现之间的递归子树可同步复制或删除，在字符串的 $v$ 与 $y$ 两个位置留下联动的可泵痕迹；这与正则泵引理只有一个循环不同，反映了栈式嵌套的结构。量词顺序仍是关键：证明者选长字符串，反方可选择任意合法分解，证明者必须为每个分解找到破坏性的泵次数。

证明 $L=\{a^n{b}^n{c}^n:n\ge 0\}$ 非上下文无关时，先由对方给出泵长度 $p$，再取 $w=a^p{b}^p{c}^p$，并应对其给出的任意合法分解。因为 $|vxy|\le p$，窗口至多跨越相邻两类字符，两个被泵片段不可能同时均衡地改变 $a,b,c$ 三种计数；选择 $i=0$ 或 $i=2$ 后，三者相等关系必被破坏。

泵引理只是上下文无关性的必要条件而非充分条件；某些非 CFL 也满足类似的泵性质，不能据此证明一个语言是 CFL。反证者不能自行指定最方便的 $v,x,y$，也不能只分析一个分解；若语言的结构对所有分解不易统一攻击，Ogden 引理往往更合适。

该引理由 上下文无关文法公理库上下文无关文法Context-free grammar · CFG每条产生式左侧是单个非终结符的生成系统。 的有限非终结符和 抽屉原理公理库鸽巢原理Pigeonhole principle · Dirichlet's box principle把多于 n 个对象放入 n 个容器时，至少一个容器包含两个对象。 导出，是排除候选 CFG/PDA、证明非上下文无关性的基本工具，也解释了单栈结构能够复制局部嵌套，却难以同步维护三个独立计数。它与 闭包性质公理库上下文无关语言闭包性质Closure properties of context-free languages上下文无关语言对并、连接、Kleene 星、同态和与正则语言求交封闭，但不对交和补封闭。 常组合使用：先用正则交或逆同态简化语言，再在规范形上实施泵引理论证；当局部窗口仍难以控制时，则可改用 Ogden 引理。