确定性下推自动机

DPDA 的每一步都由当前有限状态、下一输入符号和栈顶唯一决定，因此可以直接作为无回溯解析器运行。限制 ε 转移冲突很关键：即使每张转移表单独看像函数，只要机器可选择先做 ε 动作还是先读字符，仍然存在非确定性。确定性牺牲一部分语言表达力，换来唯一运行、补集闭包和更可预测的在线处理。输入结束标记常用于让机器知道“现在可以作最终决定”，否则前缀关系会干扰空栈式接受。

语言 $\{a^n{b}^n:n\ge 0\}$ 可由 DPDA 识别：读 a 唯一压栈，看到第一个 b 唯一切换到弹栈阶段，此后禁止再读 a。带不同类型括号的正确嵌套也可确定识别，因为每个右括号应匹配哪个左括号由栈顶唯一给出。

偶数长度回文语言 $\{w{w}^R:w\in \{0,1{\}}^{\ast }\}$ 是上下文无关的，但没有中点标记时机器无法确定何时从压栈切换到弹栈，因此不是确定性上下文无关语言。加入分隔符的 $\{w\mathrm{\#}{w}^R\}$ 则可确定识别，分隔符消除了猜测。

DPDA 是 LR、LL 等确定性解析方法的自动机基础，适合编程语言语法的单遍解析。它与一般 PDA公理库下推自动机Pushdown automaton · PDA带无界栈存储的有限控制自动机。的差距说明“文法是上下文无关的”不保证存在无回溯确定解析器。

确定性上下文无关语言具有补集闭包等良好性质，且每个 DCFL 都有无歧义文法；歧义公理库文法歧义Grammar ambiguity某个字存在两个不同语法树或最左推导时文法具有的性质。与确定解析之间因此存在紧密联系。

不过 DCFL 对并与交一般都不封闭；只能与正则语言求交后仍保证留在 DCFL。不能把 DFA 的全部布尔闭包性质直接搬到 DPDA。