形式陈述

非确定性下推自动机可定义为

$$ P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F), $$$$P=(Q,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,q_0,Z_0,F),$$

其中 $\Gamma$$\mathrm{\Gamma }$ 为栈字母表，$Z_0$$Z_0$ 为初始栈符号，且

$$ \delta:Q\times(\Sigma\cup\{\varepsilon\})\times\Gamma \to\mathcal P_{\mathrm{fin}}(Q\times\Gamma^*). $$$$\delta :Q\times (\mathrm{\Sigma }\cup \{\epsilon \})\times \mathrm{\Gamma }\to {\mathcal{P}}_{\mathrm{fin}}(Q\times {\mathrm{\Gamma }}^{\ast }).$$

一步转移可读取一个输入符号或 $\varepsilon$$\epsilon$，弹出栈顶符号并压入一个字符串。若存在消耗完整输入并到达接受状态的运行，则输入被接受。以终态接受与以空栈接受对非确定性 PDA 具有相同表达能力。

直觉

PDA 是有限自动机加一个后进先出、可无界增长的栈。栈能记住尚未匹配的嵌套层次，却不能随机访问全部历史。

例子与边界

识别 $\{0^n1^n:n\ge0\}$$\{0^n{1}^n:n\ge 0\}$ 时，读每个 $0$$0$ 压栈，随后读每个 $1$$1$ 弹栈并检查最终为空。确定性 PDA 严格弱于非确定性 PDA，尽管 DFA 与 NFA 等价；不能把有限自动机的“非确定性免费”结论照搬到 PDA。

推论与应用

非确定性 PDA 识别的语言恰为上下文无关语言，可由 CFG 与 PDA 相互构造。PDA 是编译器语法分析、递归调用栈及嵌套协议的理论模型。

参考资料

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