形式陈述

DPDA 是转移具有确定性的下推自动机。常用定义令 $\delta(q,a,X)$$\delta (q,a,X)$ 为至多一个结果，其中 $a\in\Sigma\cup\{\varepsilon\}$$a\in \mathrm{\Sigma }\cup \{\epsilon \}$；且若某 $(q,X)$$(q,X)$ 允许 $\varepsilon$$\epsilon$ 转移，就不得同时允许任何真实输入符号转移。它识别确定性上下文无关语言（DCFL）。DCFL 严格包含正则语言且严格包含于 CFL；按终态接受与按空栈接受对 DPDA 不再无条件等价。

直觉

栈提供无界但后进先出的记忆，确定性要求每一步由当前状态、下一个输入和栈顶唯一决定，不能靠“猜中一条分支”完成解析。

例子与边界

语言 $\{a^nb^n:n\ge0\}$$\{a^n{b}^n:n\ge 0\}$ 可在读 $a$$a$ 时压栈、读 $b$$b$ 时弹栈而确定性识别。回文语言 $\{ww^R\}$$\{w{w}^R\}$ 没有中点标记时通常需要猜测何时由压栈转为弹栈，不是 DCFL。DPDA 的确定性约束不仅是“每个表格单元至多一条边”，还必须排除同一状态与栈顶上 $\varepsilon$$\epsilon$ 边和读字符边的竞争。DCFL 对补封闭，但对并和交一般不封闭。

推论与应用

DPDA 是 LR 解析等确定性语法分析的自动机基础，解释了为什么许多编程语言能线性时间解析，而一般 CFG 需要更昂贵或非确定的算法。

参考资料

• John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006，Chs. 1–9。
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，Chs. 0–10。