下推自动机

有限自动机只能保留有限摘要，PDA 的栈则能记住无界但严格嵌套的信息。读左括号时压栈，读右括号时弹栈；最近打开的结构必须最先关闭，恰好匹配后进先出。非确定性还允许机器猜测输入的阶段或文法产生式。栈不是一条任意工作带：只能看和修改顶部，因此 PDA 的能力仍弱于图灵机。

识别 $\{a^n{b}^n:n\ge 0\}$ 的 PDA 在读 a 时每次压入标记 $A$，首次进入 b 阶段后每读一个 b 弹出一个 $A$；输入结束且栈回到底符号时接受。取 $q_p$ 为压栈阶段、$q_b$ 为弹栈阶段，输入 aabb 的关键配置是

再用不读输入的动作进入终态；空输入需另设接受路径。图画的是 aaabbb，比此轨迹多压入并弹出一个 $A$。若输入是 aab，读完后还剩 $A$，不能进入接受阶段；若是 aabbb，多出的 b 无法再弹出 $A$。阶段状态还禁止弹栈后重新读 a，否则只检查总数会误收 abab。平衡括号同样在左括号压栈、右括号检查并弹出匹配类型。

边界语言 $\{a^n{b}^n{c}^n:n\ge 0\}$ 需要同时保留两次独立的无界匹配，一条普通栈不足。PDA 也不能在不破坏上层内容的情况下读取栈底附近数据；把栈误作可随机访问数组会高估模型能力。

非确定性在这里也不是“免费的”：DPDA理路确定性下推自动机Deterministic pushdown automaton · DPDA每个配置至多有一个可用转移且读入与 ε 转移不冲突的下推自动机。识别的语言严格少于 NPDA 识别的全部上下文无关语言，不能把 DFA 与 NFA 的等价结论直接搬到下推自动机。

在语言表达能力上，非确定性 PDA 与上下文无关文法理路上下文无关文法Context-free grammar · CFG每条产生式左侧是单个非终结符的生成系统。等价：文法推导可由栈模拟，PDA 的接受计算也可编码为变量与产生式。转换可能显著增大表示，且确定性 PDA 并不覆盖全部上下文无关文法。

CFG–PDA 等价定理理路CFG–PDA 等价定理CFG–PDA equivalence上下文无关文法与非确定性下推自动机刻画同一语言类；三元变量描述受保护的弹栈段，完整八变量例子及双向归纳将运行转换为推导。把两态空栈机器完整转换为八个三元变量：每个变量只描述首次露出未触动下层栈的运行段，双向归纳证明生成语言保持。它还说明为什么没有终结基例的变量即使有递归规则也不能生成任何字。DPDA理路确定性下推自动机Deterministic pushdown automaton · DPDA每个配置至多有一个可用转移且读入与 ε 转移不冲突的下推自动机。限制每个配置的选择，得到严格更小但适合确定解析的语言类。

调用栈、递归下降解析、括号检查和嵌套协议监视都体现 PDA 结构；解析器实现常把文法推导状态与显式栈结合。