CFG–PDA 等价定理

文法与 PDA 是同一种嵌套机制的生成、识别两面。文法推导把尚未展开的非终结符当作待办结构，PDA 栈也保存尚待匹配或展开的任务；产生式选择对应栈顶替换，终结符匹配对应消费输入。反向构造较复杂，是因为文法必须预先概括一段运行“从某状态压着某符号开始，到哪个状态恰好弹掉它”的所有可能。非确定性承担选择产生式或猜测分解的角色。

对文法 $S\to aSb\mid \epsilon$，PDA 初始栈为 $S$。选择第一条规则把栈顶替换为 aSb，随后匹配输入 a，递归处理 $S$，最后匹配 b；选择 ε 规则结束嵌套，因此接受恰好 $a^n{b}^n$。按“剩余输入，栈顶在左的栈”记录，图中 aabb 的完整对应为

展开规则不消费输入，匹配终结符才消费输入。实现替换 $S\mapsto aSb$ 时若逐个压入，就要依次压 $b,S,a$，使 $a$ 留在栈顶。每一步均保持“已读前缀加上当前栈串，是文法能导出的句型”这一不变式；栈和输入同时为空，才得到完整推导。

边界是确定性：CFG 到 PDA 的直接构造会在一个非终结符有多条产生式时非确定选择，不能据此得到 DPDA。全部 CFL 都有 NPDA，但只有严格子类有确定 PDA；文法无歧义也不自动保证对应语言是确定性上下文无关的。

从六个动作列出全部八个变量 ​

现在从机器出发。取 $Q=\{p,q\}$、$\mathrm{\Gamma }=\{Z,A\}$、初态 $p$、初始栈 $Z$，恰有以下六个动作：

没有列出的动作均不存在。状态 $p$ 可连续读 $a$ 压入 $A$；首个 $b$ 进入 $q$，以后只能读 $b$ 弹栈。按空栈接受，输入仍须读完。尤其在初始时立即弹掉 $Z$ 的分支只接受空字，不能在还有输入时凭空结束。

三元变量恰有 $2\cdot 2\cdot 2=8$ 个。下表逐行列出全部右侧；同一行的“或”表示不同规则，无产生式不表示产生空字：

另有 $S\to [pZp]$ 与 $S\to [pZq]$，共十二条变量规则和两条开始规则。例如第一动作把 $Z$ 换成 $AZ$，所以对两个中间状态、两个终点状态各生成一条规则，正好贡献表中前两行的四条带 $a$ 规则。

在 aabb 上，机器接受运行是

完整文法中的最左推导与它对应：

最后的 $[qZq]\to \epsilon$ 对应真实的底符号弹出动作，不能删掉这一步而宣称栈已经空了。开始规则只选终点状态；其后五次展开才对应五个机器动作。

有规则不等于能产生终结字 ​

$[qZp]$、$[qAp]$ 没有规则；$[pAp]$ 的规则或者继续依赖自己，或者依赖 $[qAp]$，没有有限推导的终结基例。因此这三个变量都不能生成终结字，$[pZp]$ 也因依赖它们而不能生成。其余四个变量都有直接的终结右侧。

删去这四个不生成变量以及含它们的规则，保留下来的文法为

代入后两项并令 $B=[pAq]$，可写成 $S\to aB\mid \epsilon$、$B\to aBb\mid b$。$B$ 每次递归同时增加一个 $a$ 与一个 $b$，最后用 $b$ 结束，故生成 $a^k{b}^{k+1}$；$S$ 恰好生成 $a^n{b}^n$。这与前面的单变量文法等价，但不是说“删无用变量”一步便直接得到 $S\to aSb\mid \epsilon$。

机器上也可独立核对：读过 $a^n$ 后栈为 $A^{n}Z$，每个 $b$ 恰好去掉一个 $A$，且进入 $q$ 后不能再读 $a$。短一个 $b$ 会留栈，多一个 $b$ 没有可用动作，交错输入也无法通过。两种描述得到相同语言，而不只是恰好都接受 aabb。

为什么三元变量与受保护栈段等价 ​

先证运行推出推导，对受保护栈段的动作数作强归纳公理库强归纳法Strong induction · Complete induction归纳步可假设所有较小自然数情形成立。。零个动作不能去掉顶部的 $X$，所以没有零步情形。设首动作读取 $a$，把 $X$ 换成 $\alpha$，并进入 $r$；$a$ 可以为空。

若 $\alpha =\epsilon$，这一步已首次露出 $\beta$，由栈段定义运行必须就在此结束。因此终点是 $r$、所读字是 $a$，直接使用 $[uXr]\to a$。

若 $\alpha =Y$，首动作后剩余运行恰是去掉 $Y$ 的较短受保护段。设它消费 $x$ 并到达 $v$，归纳得到 $[rYv]{\Rightarrow }^{\ast }x$，再用 $[uXv]\to a[rYv]$。

若 $\alpha =YZ$，后续运行终将去掉这两个原栈位置。考虑首次露出未触动的 $Z\beta$的时刻：设状态为 $s$，此前在首动作之后消费 $x$，此后消费 $y$。于是运行分成

一栈顶动作不能越过尚未去掉的 $Y$ 而直接修改原 $Z$，所以这个切点存在。两段分别去掉 $Y$、$Z$，都是比原段短的受保护段；归纳得到 $[rYs]{\Rightarrow }^{\ast }x$ 和 $[sZv]{\Rightarrow }^{\ast }y$，再使用长度二规则，生成 $axy$。切点跟踪的是原有栈位置，不是碰巧出现相同字母的任意时刻。

反向证推导推出运行，对有限推导树公理库语法树Parse tree · Derivation tree用有序树记录产生式层次，以完整例子区分推导顺序、文法歧义、优先级及抽象语法树。作结构归纳。叶规则 $[uXr]\to a$ 本身就是一个真实弹栈动作。一子树规则先执行首动作，再把子树给出的运行放在 $\beta$ 上；两子树规则先把 $X$ 换成 $YZ$，把第一子树的运行放在后缀 $Z\beta$ 上，首次露出该后缀后，再把第二子树的运行放在 $\beta$ 上。它们在规则写出的中间状态 $s$ 接续，且终点之前不会触碰原 $\beta$。

这两个归纳证明所有变量的语义。取 $\beta =z=\epsilon$，再由开始规则枚举终点，便有 $L(G)=N(P)$。证明不能简单改成按输入字长归纳：ε 动作可能让非空子运行消费零个符号，字长未必严格下降。

任意机器怎样进入这个规范接口 ​

若原机器按终态接受，加入新初态 $i$、清栈态 $d$ 和新底标记 $\mathrm{\perp }$。新机器初始栈为 $\mathrm{\perp }$，先用 ε 动作替换为 $Z_0\mathrm{\perp }$ 并进入原 $q_0$。原动作照旧，但它们不能匹配新增 $\mathrm{\perp }$。

从每个原终态 $f$，对每个 $X\in \mathrm{\Gamma }\cup \{\mathrm{\perp }\}$，允许 ε 弹出 $X$ 并进入 $d$；$d$ 再以 ε 动作逐个弹栈，没有读字符动作或返回旧状态的出口。只有这个阶段能弹掉新底标记。原来在非终态弹空旧栈不会误收；原来在终态且旧栈已空，也可以通过弹 $\mathrm{\perp }$ 接受。

原接受运行后接清栈，就得到新接受运行。反之，新接受运行必须从某个原终态进入清栈，而清栈不消费输入；既然最终输入读完，进入时便已读完，之前的模拟就是原接受运行。允许提前猜测进入清栈不会误收，因为剩余输入无法再被消费。这一证明没有假设机器能主动检测“输入已经结束”。

若某动作替换为 $Y_1\cdots Y_k$、$k\ge 3$，可以为它增加专用控制状态 $c_{k-1},\dots ,c_2$，记 $c_1=r$。第一步按原动作读取 $a$，把 $X$ 换成 $Y_{k-1}{Y}_k$ 并进入 $c_{k-1}$；随后对 $j=k-1,\dots ,2$，仅允许

栈依次成为 $Y_{k-1}{Y}_k\beta ,\dots ,Y_1\cdots Y_k\beta$，输入只在首步消费。新状态没有别的出口，中间也不会露出 $\beta$，所以整个链恰好模拟一个旧动作。每步替换长度不超过二，无需凭空在空栈上压入符号。

若规范化后有 $n$ 个状态、$g$ 个栈符号和 $t$ 个动作，三元变量数为 $n^{2}g$，加上新开始符号；每个长度二动作产生 $n^2$ 条规则，长度一产生 $n$ 条，弹栈动作只产生一条。这解释了为什么语言等价不意味着表示大小相近。

定理把上下文无关文法公理库上下文无关文法Context-free grammar · CFG每条产生式左侧是单个非终结符的生成系统。的生成视角与下推自动机公理库下推自动机Pushdown automaton · PDA带无界栈存储的有限控制自动机。的运行视角统一起来。可用文法闭包与范式证明语言性质，也可用栈机器设计识别算法。

编译原理中，语法规格被转换为带栈解析器；在理论上，该等价支撑 CFL 的成员判定、闭包分析和与确定 PDA公理库确定性下推自动机Deterministic pushdown automaton · DPDA每个配置至多有一个可用转移且读入与 ε 转移不冲突的下推自动机。子类的比较。

终点自测：从六动作表独立列出十四条规则，标出四个不能生成终结字的变量，写出 aabb 的运行及最左推导；再说明二符号替换的中间状态对应哪个首次弹栈边界，以及为何 ε 动作迫使证明采用运行步数而非输入长度。