下推自动机

Template:Cleanup-jargon 在自动机理论中，下推自动机（Template:Lang-en）是使用了包含数据的栈的有限自动机。

综述

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

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

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

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

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

形式定义

PDA 形式定义为 6-元组：

$M=(Q,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,q_0,F)$ 这里的

• $Q$ 是状态的有限集合
• $\mathrm{\Sigma }$ 是输入字母表的有限集合
• $\mathrm{\Gamma }$ 是栈字母表的有限集合
• $\delta$: $Q\times {\mathrm{\Sigma }}_{ϵ}\times {\mathrm{\Gamma }}_{ϵ}⟶𝒫(Q\times {\mathrm{\Gamma }}_{ϵ})$ 是转移函数
• $q_0$ 是“开始状态”
• $F\subset Q$ 是“接受状态”的集合
• ${\mathrm{\Gamma }}_{ϵ}=\mathrm{\Gamma }\cup \{ϵ\}$
• ${\mathrm{\Sigma }}_{ϵ}=\mathrm{\Sigma }\cup \{ϵ\}$

计算定义 1

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

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

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

(ii) $\mathrm{\exists }{s}_0,s_1,s_2,s_3,\cdots ,s_n\in {\mathrm{\Gamma }}^{*}$ 使得

$s_i=a_{i+1}{t}_i,s_{i+1}=b_{i+1}{t}_i,t_i\in {\mathrm{\Gamma }}^{*}$

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

$a_{i+1}$ 和 $b_{i+1}$ 二者都可以 $ϵ$。

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

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

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

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

注意当 n=0 时，计算路径就是单元素集合 $(q_0)$。

计算定义 2

对于任何输入 $w=w_1{w}_2\cdots w_m,w_i\in \mathrm{\Sigma },m\ge 0$，M 接受 w，如果存在计算路径 $(q_0,q_1,....,q_n)$ 和有限序列 $r_0,r_1,r_2,\cdots r_m\in Q,m\le n$，使得

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

$\mathrm{\exists }f(i)$ 这里的 $i\le f(i)\le n$ 使得 $r_i=q_{f(i)}$

(ii) $(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。

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

(iii) $(q_{j+1},b_{j+1})\in \delta (q_j,ϵ,a_{j+1})$，如果 $q_j\notin \{r_0,r_1,\cdots r_m\}$

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

(iv) $r_m=q_n$ 且 $r_m\in F$

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

例子

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

$M=(Q,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,q_1,F)$

• $Q=\{q_1,q_2,q_3,q_4\}$

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

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

• $F=\{q_1,q_4\}$

• $\delta (q_1,ϵ,ϵ)=\{(q_2,\mathrm{\$}),(q_1,ϵ)\}$

• $\delta (q_2,0,ϵ)=\{(q_2,0)\}$

• $\delta (q_2,1,0)=\{(q_3,ϵ)\}$

• $\delta (q_3,1,0)=\{(q_3,ϵ)\}$

• $\delta (q_3,ϵ,\mathrm{\$})=\{(q_4,ϵ)\}$

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

理解计算过程

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

(a) 输入字符串 = 0011

(i) 写 $\delta$(q₁, $ϵ$, $ϵ$) $\to$ (q₂, $) 来表示 (q₂, $) $\in$ $\delta$(q₁, $ϵ$, $ϵ$)

s₀ = $ϵ$, s₁ = $, t = $ϵ$, a = $ϵ$, b = $

设置 r₀ = q₂

(ii) $\delta$(r₀, 0, $ϵ$) = $\delta$(q₂, 0, $ϵ$) $\to$ (q₂, 0)

s₁ = $, a = $ϵ$, t = $, b = 0, s₂ = 0$

设置 r₁ = q₂

(iii) $\delta$(r₁, 0, $ϵ$) = $\delta$(q₂, 0, $ϵ$) $\to$ (q₂, 0)

s₂ = 0$, a = $ϵ$, t = 0$, b = 0, s₃ = 00$

设置 r₂ = q₂

(iv) $\delta$(r₂, 1, 0) = $\delta$(q₂, 1, 0) $\to$ (q₃, $ϵ$)

s₃ = 00$, a = 0, t = 0$, b = $ϵ$, s₄ = 0$

设置 r₃ = q₃

(v) $\delta$(r₃, 1, 0) = $\delta$(q₃, 1, 0) $\to$ (q₃, $ϵ$)

s₄ = 0$, a = 0, t = $, b = $ϵ$, s₅ = $

(vi) $\delta$(q₃, $ϵ$, $) $\to$ (q₄, $ϵ$)

s₅ = $, a = $, t = $ϵ$, b = $ϵ$, s₆ = $ϵ$

设置 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) $\delta$(r₃, $ϵ$, a) = $\delta$(q₃, $ϵ$, a)

因为 s₄ = 0$，要么 a = $ϵ$ 要么 a = 0

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

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

(c) 输入字符串 = $ϵ$

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

$\delta$(r₀, $ϵ$, $ϵ$) $\to$ (q₁, $ϵ$)

因为 q₁ 是接受状态，$ϵ$ 被接受。

广义下推自动机(GPDA)

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

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

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

$\delta$: $Q\times {\mathrm{\Sigma }}_{ϵ}\times {\mathrm{\Gamma }}^{*}⟶𝒫(Q\times {\mathrm{\Gamma }}^{*})$ 是转移函数。

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

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

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

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

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

构造 PDA 的下列转移：

${\delta }^{\text{'}}$(q₁, w, x₁) $⟶$ (p₁, $ϵ$)

${\delta }^{\text{'}}$(p₁, $ϵ$, x₂) $⟶$ (p₂, $ϵ$)

$⋮$

${\delta }^{\text{'}}$(p_m-1, $ϵ$, x_m) $⟶$ (p_m, $ϵ$)

${\delta }^{\text{'}}$(p_m, $ϵ$, $ϵ$ ) $⟶$ (p_m+1, y_n)

${\delta }^{\text{'}}$(p_m+1, $ϵ$, $ϵ$ ) $⟶$ (p_m+2, y_n-1)

$⋮$

${\delta }^{\text{'}}$(p_m+n-1, $ϵ$, $ϵ$ ) $⟶$ (q₂, y₁)

参见

• 堆叠结构机器
• 确定下推自动机
• 有限自动机
• 上下文无关文法

外部链接

• non-deterministic pushdown automaton, on Planet Math.
• JFLAPTemplate:Wayback，simulator for several types of automata including nondeterministic pushdown automata

参考书目

• 《自动机理论、语言和计算导引》，John E. Hopcroft，Jeffery D. Ullman，徐美瑞译，洪加威校，科学出版社，1986年
• Template:Cite book Section 2.2: Pushdown Automata, pp.101–114.