形式陈述

对语言 $L\subseteq\Sigma^*$$L\subseteq {\mathrm{\Sigma }}^{\ast }$，以下条件等价：存在上下文无关文法 $G$$G$ 使 $L=L(G)$$L=L(G)$；存在非确定型下推自动机 $P$$P$ 使 $L=L(P)$$L=L(P)$。从文法到 PDA，可先把开始符号压栈，再非确定地以产生式替换栈顶非终结符，并用输入符号匹配栈顶终结符；从 PDA 到文法，可令非终结符编码“从状态 $p$$p$、栈符号 $A$$A$ 出发，恰好弹出 $A$$A$ 并到达状态 $q$$q$”的计算片段。按终态接受与按空栈接受的 NPDA 也可互相转换。

直觉

文法自顶向下展开一棵推导树，PDA 则用栈保存尚未完成的嵌套任务；两种表示都只有一个后进先出的无界记忆，因此能力恰好一致。

例子与边界

文法 $S\to 0S1\mid\varepsilon$$S\to 0S1\mid \epsilon$ 生成 $\{0^n1^n:n\ge0\}$$\{0^n{1}^n:n\ge 0\}$；对应 PDA 每读一个 $0$$0$ 压入标记，随后每读一个 $1$$1$ 弹出一个标记。等价性依赖非确定性：确定型 PDA 识别的确定型上下文无关语言严格少于全部 CFL。转换通常增加状态或变量，不保证大小保持不变。

推论与应用

定理允许在语法分析、闭包性质和不可判定性证明中自由选择更合适的表示。CFG 适合描述递归语法与构造推导，PDA 适合描述在线识别和栈行为；CYK、LL/LR 等算法则进一步限制文法形式或确定性。

参考资料

• John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006，Chs. 5–6, pushdown automata and context-free grammars。
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，Ch. 2, equivalence of pushdown automata and context-free grammars。