“CFG–PDA 等价定理说明 PDA 恰好识别上下文无关语言。DPDA限制每个配置的选择，得到严格更小但适合确定解析的语言类。”
形式陈述
CFG–PDA 等价定理断言：语言
从 CFG 到 PDA，可把开始符号压栈；栈顶为非终结符
从 PDA 到 CFG，可先规范化转移，再引入非终结符
对 NPDA，按终态接受与按空栈接受也可通过加入新初态、栈底标记和清栈阶段相互转换。上述双向构造保证语言相同，但通常会增加状态、栈符号或文法变量，不保证表示规模保持不变。
直觉
文法与 PDA 是同一种嵌套机制的生成、识别两面。文法推导把尚未展开的非终结符当作待办结构，PDA 栈也保存尚待匹配或展开的任务；产生式选择对应栈顶替换，终结符匹配对应消费输入。反向构造较复杂，是因为文法必须预先概括一段运行“从某状态压着某符号开始，到哪个状态恰好弹掉它”的所有可能。非确定性承担选择产生式或猜测分解的角色。
例子与边界
对文法 aSb，随后匹配输入 a，递归处理 b；选择 ε 规则结束嵌套，因此接受恰好
边界是确定性：CFG 到 PDA 的直接构造会在一个非终结符有多条产生式时非确定选择，不能据此得到 DPDA。全部 CFL 都有 NPDA，但只有严格子类有确定 PDA；文法无歧义也不自动保证对应语言是确定性上下文无关的。
推论与应用
定理把上下文无关文法的生成视角与下推自动机的运行视角统一起来。可用文法闭包与范式证明语言性质，也可用栈机器设计识别算法。
编译原理中，语法规格被转换为带栈解析器；在理论上，该等价支撑 CFL 的成员判定、闭包分析和与确定 PDA子类的比较。
参考资料
- 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。