下推自动机

下推自动机比有限状态自动机复杂：除了有限状态组成部分外，还包括一个长度不受限制的栈；下推自动机的状态迁移不但要参考有限状态部分，也要参照栈当前的状态；状态迁移不但包括有限状态的变迁，还包括一个栈的出栈或入栈过程。下推自动机可以形象的理解为，借由加上读取一个容量无限栈的能力，扩充一个能做${\displaystyle \epsilon }$ -转移的非确定有限状态自动机。

下推自动机存在“确定”与“非确定”两种形式，两者并不等价。（对有限状态自动机两者是等价的）

每一个下推自动机都接受一个形式语言。被“非确定下推自动机”接受的语言是上下文无关语言。

如果我们把下推自动机扩展，允许一个有限状态自动机存取两个栈，我们得到一个能力更强的自动机，这个自动机与图灵机等价。

下推自动机作为一个形式系统最早于1961年出现在 Oettinger 的论文中。它与上下文无关文法的等价性是由乔姆斯基于1962年发现的。

PDA 形式定义为 6-元组：

${\displaystyle M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{0},\ F)}$  这里的

• ${\displaystyle \,Q}$  是状态的有限集合
• ${\displaystyle \,\Sigma }$  是输入字母表的有限集合
• ${\displaystyle \,\Gamma }$  是栈字母表的有限集合
• ${\displaystyle \,\delta }$ : ${\displaystyle Q\times \Sigma _{\epsilon }\times \Gamma _{\epsilon }\longrightarrow {\mathcal {P}}(Q\times \Gamma _{\epsilon })}$  是转移函数
• ${\displaystyle q_{0}}$  是“开始状态”
• ${\displaystyle F\subset Q}$  是“接受状态”的集合
• ${\displaystyle \Gamma _{\epsilon }=\Gamma \cup \{\epsilon \}}$ 
• ${\displaystyle \Sigma _{\epsilon }=\Sigma \cup \{\epsilon \}}$ 

计算定义 1

对于任何 PDA ${\displaystyle M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{0},\ F)}$ ，计算路径是一个有序的（n+1）-元组 ${\displaystyle (q_{0},\,q_{1},....,\,q_{n})}$ ，这里的 ${\displaystyle q_{i}\in Q,n\geq 0}$ ，它满足如下条件：

(i) ${\displaystyle \ \ (q_{i+1},b_{i+1})\in \delta (q_{i},w_{i+1},a_{i+1})}$  对于 i = 0, 1, 2,......, n-1,

这里的 ${\displaystyle w_{i+1}\in \Sigma _{\epsilon },\ a_{i+1},\ b_{i+1}\in \Gamma _{\epsilon }}$ 

(ii) ${\displaystyle \exists \,s_{0},\,s_{1},\,s_{2},\,s_{3},\,\cdots ,\,s_{n}\,\in \Gamma ^{*}}$  使得

${\displaystyle s_{i}=a_{i+1}t_{i},\,s_{i+1}=b_{i+1}t_{i},\,t_{i}\in \Gamma ^{*}}$ 

在直觉上，PDA 在计算过程中任何一点上都面对着多种可能性，从栈顶读一个符号并把它替代为另一个符号，从栈顶读一个符号并删除它而不替换，不从栈顶读任何符号但压入另一个符号进去，或什么都不做。所有这些都同时由等式 ${\displaystyle s_{i}=a_{i+1}t_{i}\,}$  和 ${\displaystyle s_{i+1}=b_{i+1}t_{i}\,}$  来支配。${\displaystyle s_{i}\,}$  是紧接在第 i+1 次转移移动之前的栈内容，而 ${\displaystyle a_{i+1}\,}$  是要从栈顶去除的符号。${\displaystyle s_{i+1}\,}$  是紧接在第 i+1 次转移移动之后栈内容，而 ${\displaystyle b_{i+1}\,}$  是在第 i+1 次转移移动期间要增加到栈上的符号。

${\displaystyle a_{i+1}\,}$  和 ${\displaystyle b_{i+1}\,}$  二者都可以 ${\displaystyle \epsilon \,}$ 。

如果 ${\displaystyle a_{i+1}\neq \epsilon \,}$  而 ${\displaystyle b_{i+1}\neq \epsilon \,}$ ，则 PDA 从栈读一个符号并把它替代为另一个符号。

如果 ${\displaystyle a_{i+1}\neq \epsilon \,}$  而 ${\displaystyle b_{i+1}=\epsilon \,}$ ，则 PDA 从栈读一个符号并删除它而不替换。

如果 ${\displaystyle a_{i+1}=\epsilon \,}$  而 ${\displaystyle b_{i+1}\neq \epsilon \,}$ ，则 PDA 简单的增加一个符号到栈上。

如果 ${\displaystyle a_{i+1}=\epsilon \,}$  而 ${\displaystyle b_{i+1}=\epsilon \,}$ ，则 PDA 保持栈不变动。

注意当 n=0 时，计算路径就是单元素集合 ${\displaystyle (q_{0})\,}$ 。

计算定义 2

对于任何输入 ${\displaystyle w=w_{1}w_{2}\cdots w_{m},\ w_{i}\in \Sigma ,m\geq 0}$ ，M 接受 w，如果存在计算路径 ${\displaystyle (q_{0},\,q_{1},....,\,q_{n})\,}$  和有限序列 ${\displaystyle r_{0},r_{1},r_{2},\cdots r_{m}\in Q,\ m\leq n}$ ，使得

(i) 对于每个 i = 0, 1, 2,...m，${\displaystyle r_{i}\,}$  都在计算路径上。就是说

${\displaystyle \exists f(i)}$  这里的 ${\displaystyle i\leq f(i)\leq n}$  使得 ${\displaystyle r_{i}=q_{f(i)}\,}$ 

(ii) ${\displaystyle (q_{f(i)+1},b_{f(i)+1})\in \delta (r_{i},w_{i+1},a_{f(i)+1})}$  对于每个 i = 0, 1, 2,...m-1。

这里的 ${\displaystyle a_{f(i)+1}\,}$  和 ${\displaystyle b_{f(i)+1}\,}$  定义同于计算定义 1。

(iii) ${\displaystyle (q_{j+1},b_{j+1})\in \delta (q_{j},\epsilon ,a_{j+1})}$ ，如果 ${\displaystyle q_{j}\notin \{r_{0},r_{1},\cdots r_{m}\}}$ 

这里的 ${\displaystyle a_{j+1}\,}$  和 ${\displaystyle b_{j+1}\,}$  定义同于计算定义 1。

(iv) ${\displaystyle r_{m}=q_{n}\,}$  且 ${\displaystyle r_{m}\in F}$ 

注意上述定义不提供测试空栈的机制。要这么做你需要在所有计算开始前在栈上写一个特殊符号，使得 PDA 可以在检测到这个符号的时候有效的识别出栈已经空了。形式的说，实现它可通过介入转移 ${\displaystyle \delta (q_{0},\epsilon ,\,\epsilon )=\{(q_{1},\$)\}}$ 这里的 $ 是特殊符号。

下面是识别语言 ${\displaystyle \{0^{n}1^{n}|n\geq 0\}}$  的 PDA 的形式描述：

${\displaystyle M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{1},\ F)}$ 

• ${\displaystyle Q=\{q_{1},q_{2},q_{3},q_{4}\}\,}$ 

• ${\displaystyle \Sigma =\{0,1\}\,}$ 

• ${\displaystyle \Gamma =\{0,\$\}\,}$ 

• ${\displaystyle F=\{q_{1},q_{4}\}\,}$ 

• ${\displaystyle \delta (q_{1},\epsilon ,\epsilon )=\{(q_{2},\$),(q_{1},\epsilon )\}\,}$ 

• ${\displaystyle \delta (q_{2},0,\epsilon )=\{(q_{2},0)\}\,}$ 

• ${\displaystyle \delta (q_{2},1,0)=\{(q_{3},\epsilon )\}\,}$ 

• ${\displaystyle \delta (q_{3},1,0)=\{(q_{3},\epsilon )\}\,}$ 

• ${\displaystyle \delta (q_{3},\epsilon ,\$)=\{(q_{4},\epsilon )\}\,}$ 

• ${\displaystyle \delta (q,w,a)=\varnothing }$  对于任何其他状态、输入和栈符号的值。

理解计算过程

下面展示上述 PDA 如何计算不同的输入字符串。

(a) 输入字符串 = 0011

(i) 写 ${\displaystyle \delta }$ (q₁, ${\displaystyle \epsilon }$ , ${\displaystyle \epsilon }$ ) ${\displaystyle \rightarrow }$  (q₂, $) 来表示 (q₂, $) ${\displaystyle \in }$  ${\displaystyle \delta }$ (q₁, ${\displaystyle \epsilon }$ , ${\displaystyle \epsilon }$ )

s₀ = ${\displaystyle \epsilon }$ , s₁ = $, t = ${\displaystyle \epsilon }$ , a = ${\displaystyle \epsilon }$ , b = $

设置 r₀ = q₂

(ii) ${\displaystyle \delta }$ (r₀, 0, ${\displaystyle \epsilon }$ ) = ${\displaystyle \delta }$ (q₂, 0, ${\displaystyle \epsilon }$ ) ${\displaystyle \rightarrow }$  (q₂, 0)

s₁ = $, a = ${\displaystyle \epsilon }$ , t = $, b = 0, s₂ = 0$

设置 r₁ = q₂

(iii) ${\displaystyle \delta }$ (r₁, 0, ${\displaystyle \epsilon }$ ) = ${\displaystyle \delta }$ (q₂, 0, ${\displaystyle \epsilon }$ ) ${\displaystyle \rightarrow }$  (q₂, 0)

s₂ = 0$, a = ${\displaystyle \epsilon }$ , t = 0$, b = 0, s₃ = 00$

设置 r₂ = q₂

(iv) ${\displaystyle \delta }$ (r₂, 1, 0) = ${\displaystyle \delta }$ (q₂, 1, 0) ${\displaystyle \rightarrow }$  (q₃, ${\displaystyle \epsilon }$ )

s₃ = 00$, a = 0, t = 0$, b = ${\displaystyle \epsilon }$ , s₄ = 0$

设置 r₃ = q₃

(v) ${\displaystyle \delta }$ (r₃, 1, 0) = ${\displaystyle \delta }$ (q₃, 1, 0) ${\displaystyle \rightarrow }$  (q₃, ${\displaystyle \epsilon }$ )

s₄ = 0$, a = 0, t = $, b = ${\displaystyle \epsilon }$ , s₅ = $

(vi) ${\displaystyle \delta }$ (q₃, ${\displaystyle \epsilon }$ , $) ${\displaystyle \rightarrow }$  (q₄, ${\displaystyle \epsilon }$ )

s₅ = $, a = $, t = ${\displaystyle \epsilon }$ , b = ${\displaystyle \epsilon }$ , s₆ = ${\displaystyle \epsilon }$ 

设置 r₄ = q₄

因为 q₄ 是接受状态，0011 被接受。

作为总结，计算路径 = (q₁, q₂, q₂, q₂, q₃, q₃, q₄)

而 (r₀, r₁, r₂, r₃, r₄) = (q₂, q₂, q₂, q₃, q₄)

(b) 输入字符串 = 001

计算移动 (i), (ii), (iii), (iv) 将必定同于情况 (a)，否则，PDA 在到达 (v) 之前就已经进入死胡同。

(v) ${\displaystyle \delta }$ (r₃, ${\displaystyle \epsilon }$ , a) = ${\displaystyle \delta }$ (q₃, ${\displaystyle \epsilon }$ , a)

因为 s₄ = 0$，要么 a = ${\displaystyle \epsilon }$  要么 a = 0

在任何一种情况下，${\displaystyle \delta }$ (q₃, ${\displaystyle \epsilon }$ , a) = ${\displaystyle \varnothing }$ 

因此计算在 r₃ = q₃ 进入死胡同，这不是接受状态。所以 001 被拒绝。

(c) 输入字符串 = ${\displaystyle \epsilon }$ 

设置 r₀ = q₁, r₁ = q₁

${\displaystyle \delta }$ (r₀, ${\displaystyle \epsilon }$ , ${\displaystyle \epsilon }$ ) ${\displaystyle \rightarrow }$  (q₁, ${\displaystyle \epsilon }$ )

因为 q₁ 是接受状态，${\displaystyle \epsilon }$  被接受。

GPDA 是在一个步骤内写入整个字符串到栈上或从栈上去除整个字符串的 PDA。

GPDA 形式定义为 6-元组 ${\displaystyle M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{0},\ F)}$ 

这里的 Q, ${\displaystyle \Sigma \,}$ , ${\displaystyle \Gamma \,}$ , q₀ 和 F 的定义同于 PDA。

${\displaystyle \,\delta }$ : ${\displaystyle Q\times \Sigma _{\epsilon }\times \Gamma ^{*}\longrightarrow {\mathcal {P}}(Q\times \Gamma ^{*})}$  是转移函数。

GPDA 的计算规则同于 PDA，除了 a_i+1 和 b_i+1 现在是字符串而不是符号之外。

GPDA 和 PDA 是等价的，如果一个语言可被一个 PDA 识别，它也可被一个 GPDA 识别，反之亦然。

可以使用下列模拟公式化对 GPDA 和 PDA 的等价性的一个分析式证明：

设 ${\displaystyle \delta }$ (q₁, w, x₁x₂...x_m) ${\displaystyle \longrightarrow }$  (q₂, y₁y₂...y_n) 是 GPDA 的转移。

这里的 q₁, q₂ ${\displaystyle \in }$  Q, w ${\displaystyle \in \Sigma _{\epsilon }\,}$ , x₁x₂...x_m ${\displaystyle \in \Gamma ^{*}}$ , m${\displaystyle \geq }$ 0, y₁y₂...y_n ${\displaystyle \in \Gamma ^{*}}$ , n${\displaystyle \geq }$ 0。

构造 PDA 的下列转移：

${\displaystyle \delta ^{'}}$ (q₁, w, x₁) ${\displaystyle \longrightarrow }$  (p₁, ${\displaystyle \epsilon }$ )

${\displaystyle \delta ^{'}}$ (p₁, ${\displaystyle \epsilon }$ , x₂) ${\displaystyle \longrightarrow }$  (p₂, ${\displaystyle \epsilon }$ )

${\displaystyle \vdots }$ 

${\displaystyle \delta ^{'}}$ (p_m-1, ${\displaystyle \epsilon }$ , x_m) ${\displaystyle \longrightarrow }$  (p_m, ${\displaystyle \epsilon }$ )

${\displaystyle \delta ^{'}}$ (p_m, ${\displaystyle \epsilon }$ , ${\displaystyle \epsilon }$  ) ${\displaystyle \longrightarrow }$  (p_m+1, y_n)

${\displaystyle \delta ^{'}}$ (p_m+1, ${\displaystyle \epsilon }$ , ${\displaystyle \epsilon }$  ) ${\displaystyle \longrightarrow }$  (p_m+2, y_n-1)

${\displaystyle \vdots }$ 

${\displaystyle \delta ^{'}}$ (p_m+n-1, ${\displaystyle \epsilon }$ , ${\displaystyle \epsilon }$  ) ${\displaystyle \longrightarrow }$  (q₂, y₁)

• 确定下推自动机
• 有限状态自动机
• 上下文无关文法

• non-deterministic pushdown automaton, on Planet Math.
• JFLAP（页面存档备份，存于互联网档案馆），simulator for several types of automata including nondeterministic pushdown automata

• 《自动机理论、语言和计算导引》，John E. Hopcroft，Jeffery D. Ullman，徐美瑞译，洪加威校，科学出版社，1986年
• Michael Sipser. Introduction to the Theory of Computation. PWS Publishing. 1997. ISBN 978-0-534-94728-6.  Section 2.2: Pushdown Automata, pp.101–114.