上下文无关语言泵引理

形式陈述

若 $L$ 能由上下文无关文法生成，则存在整数泵长度 $p\ge1$ ，使每个满足 $|w|\ge p$ 的 $w\in L$ 都可分解为

w=uvxyz,

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

uv^ixy^iz\in L.

这里 $u,v,x,y,z$ 都是字，允许其中某些为空，但 $v,y$ 不能同时为空。量词顺序是 $\exists p\;\forall w\;\exists(u,v,x,y,z)\;\forall i$ ，其中 $w$ 限于语言中的长字。要反证，必须对每个候选 $p$ 找到一个长字，再对它的每个合法分解找到失败的 $i$ ；选一个坏分解不够。

先用Chomsky 范式保留同一语言及受控空字例外。设范式文法有 $m\ge1$ 个非终结符，取 $p=2^m$ 。把非空字的一棵完整语法树中终结符产生式的单边收缩，得到以非终结符节点为骨架的二叉树；若每条根到叶路径至多有 $m$ 个这样的节点，终结字长度至多 $2^{m-1}<p$ 。因此对 $|w|\ge p$ ，最长路径至少含 $m+1$ 个非终结符节点。

在该最长路径最后 $m+1$ 个非终结符节点中，用鸽巢原理选出两次出现的同一个 $A$ 。较高的 $A$ 以下最长路径至多含 $m+1$ 个非终结符节点，所以其整棵子树至多有 $2^m=p$ 个终结符叶；把它的产出写成 $vxy$ ，其中较低的 $A$ 产出 $x$ ，便有 $|vxy|\le p$ 。

两次出现之间至少经过一次二叉分裂。偏离选定路径的孩子子树在这棵完整树中产生非空字：范式没有内部空产生式，受控的空字规则只可能位于不再出现在右侧的新开始符号。因此 $v,y$ 至少一个非空。原树给出 $S\Rightarrow^*uAz$ 、 $A\Rightarrow^*vAy$ 与 $A\Rightarrow^*x$ ；重复中间展开 $i$ 次再用最后一棵子树收尾，就得到 $uv^ixy^iz$ 。 $i=0$ 是直接用较低子树替换较高子树，故删除情形也成立。

直觉

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

例子与边界

证明 $L=\{a^nb^nc^n:n\ge0\}$ 非上下文无关时，先由对方给出泵长度 $p$ ，再取 $w=a^pb^pc^p$ ，并应对其给出的任意合法分解。若连续窗口同时含有 $a$ 和 $c$ ，它必须包括中间全部 $p$ 个 $b$ ，加上两端字符至少长 $p+2$ ，与 $|vxy|\le p$ 矛盾。因此窗口至少完全避开一种字符。取 $i=0$ ，从原字删去 $v,y$ ：被避开的那种字符仍有 $p$ 个，而因 $|vy|>0$ ，至少另一种字符减少了。删除不会打乱剩余字符的先后顺序，却必定打破三种计数相等，故 $uxz\notin L$ 。这一论证覆盖所有合法分解，包括 $v$ 或 $y$ 单独为空、以及窗口跨越两段交界的情况，矛盾完成。

对照一个合法泵送：在 $\{a^nb^n:n\ge0\}$ 中取 $w=aaabbb$ ，令 $u=aa,v=a,x=\varepsilon,y=b,z=bb$ ，则 $uv^ixy^iz=a^{i+2}b^{i+2}$ 。删除一层或增加一层都保留匹配；并不要求所有分解都如此。

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

推论与应用

该引理由上下文无关文法的有限非终结符和抽屉原理导出，是排除候选 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。
OpenDSA Project Contributors, Formal Languages With Visualizations: Properties of Context-Free Languages, 2019，§8.1.1，泵引理与三个计数反例。

形式陈述 ​

反向链接

形式陈述