下推自动机

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

识别 $\{a^n{b}^n:n\ge 0\}$ 的 PDA 在读 a 时每次压入标记 $A$，首次进入 b 阶段后每读一个 b 弹出一个 $A$；输入结束且栈回到底符号时接受。平衡括号同样在左括号压栈、右括号检查并弹出匹配类型。

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

非确定性在这里也不是“免费的”：DPDA 识别的语言严格少于 NPDA 识别的全部上下文无关语言，不能把 DFA 与 NFA 的等价结论直接搬到下推自动机。

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

CFG–PDA 等价定理公理库CFG–PDA 等价定理CFG–PDA equivalence上下文无关文法生成的语言恰为下推自动机接受的语言。说明 PDA 恰好识别上下文无关语言。DPDA公理库确定性下推自动机Deterministic pushdown automaton · DPDA每个配置至多有一个可用转移且读入与 ε 转移不冲突的下推自动机。限制每个配置的选择，得到严格更小但适合确定解析的语言类。

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