下推自动机

维基百科，自由的百科全书

在自动机理论中，下推自动机(PDA)是使用了包含数据的栈的有限自动机。

[编辑] 综述

下推自动机比有限状态自动机复杂：除了有限状态组成部分外，还包括一个长度不受限制的栈；下推自动机的状态迁移不但要参考有限状态部分，也要参照栈当前的状态；状态迁移不但包括有限状态的变迁，还包括一个栈的出栈或入栈过程。下推自动机可以形象的理解为，藉由加上讀取一個容量無限堆疊的能力，擴充一個能做 $ε$ -轉移的非確定有限狀態自動機。

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

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

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

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

[编辑] 形式定义

PDA 形式定义为 6-元组:

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

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

计算定义 1

对于任何 PDA $M=(Q,\ \Sigma,\ \Gamma,\ \delta, \ q_{0}, \ F)$ ，计算路径是一个有序的(n+1)-元组 $(q_{0},\, q_{1}, ...., \,q_{n})$ ，这里的 $q_{i} \in Q, n \geq 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 \Sigma_{\epsilon}, \ a_{i+1}, \ b_{i+1}\in \Gamma_{\epsilon}$

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

$s_{i} = a_{i+1}t_{i},\,s_{i+1} = b_{i+1}t_{i},\, t_{i}\in\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} \,$ 二者都可以 $\epsilon \,$ 。

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

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

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

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

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

计算定义 2

对于任何输入 $w = w_1w_2 \cdots w_m, \ w_i \in \Sigma , m \geq 0$ ，M 接受 w，如果存在计算路径 $(q_{0},\, q_{1}, ...., \,q_{n}) \,$ 和有限序列 $r_0, r_1, r_2,\cdots r_m \in Q, \ m \leq n$ ，使得

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

$\exists f(i)$ 这里的 $i \leq f(i) \leq 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, \epsilon, 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, \epsilon,\,\epsilon) = \{(q_1, $)\}$ 这里的 $ 是特殊符号。

[编辑] 例子

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

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

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

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

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

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

$\delta (q_1, \epsilon, \epsilon) = \{ (q_2, $), (q_1, \epsilon) \} \,$

$\delta (q_2, 0, \epsilon) = \{ (q_2, 0) \} \,$

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

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

$\delta (q_3, \epsilon, $) = \{ (q_4, \epsilon) \} \,$

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

[编辑] 理解计算过程

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

(a) 输入字符串 = 0011

(i) 写

δ

(q₁,

ε

ε

) $\rightarrow$ (q₂, $) 来表示 (q₂, $) $\in$

δ

(q₁,

ε

ε

)

s₀ =

ε

, s₁ = $, t =

ε

, a =

ε

, b = $

设置 r₀ = q₂

(ii)

δ

(r₀, 0,

ε

) =

δ

(q₂, 0,

ε

) $\rightarrow$ (q₂, 0)

s₁ = $, a =

ε

, t = $, b = 0, s₂ = 0$

设置 r₁ = q₂

(iii)

δ

(r₁, 0,

ε

) =

δ

(q₂, 0,

ε

) $\rightarrow$ (q₂, 0)

s₂ = 0$, a =

ε

, t = 0$, b = 0, s₃ = 00$

设置 r₂ = q₂

(iv)

δ

(r₂, 1, 0) =

δ

(q₂, 1, 0) $\rightarrow$ (q₃,

ε

)

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

ε

, s₄ = 0$

设置 r₃ = q₃

(v)

δ

(r₃, 1, 0) =

δ

(q₃, 1, 0) $\rightarrow$ (q₃,

ε

)

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

ε

, s₅ = $

(vi)

δ

(q₃,

ε

, $) $\rightarrow$ (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)

δ

(r₃,

ε

, a) =

δ

(q₃,

ε

, a)

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

ε

要么 a = 0

在任何一种情况下，

δ

(q₃,

ε

, a) = $\varnothing$

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

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

δ

(r₀,

ε

ε

) $\rightarrow$ (q₁,

ε

)

因为 q₁ 是接受状态，

ε

被接受。

[编辑] 广义下推自动机(GPDA)

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

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

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

$\,\delta$ : $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 的等价性的一个分析式证明:

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

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

构造 PDA 的下列转移:

δ'

(q₁, w, x₁) $\longrightarrow$ (p₁,

ε

)

δ'

(p₁,

ε

, x₂) $\longrightarrow$ (p₂,

ε

)

$\vdots$

δ'

(p_m-1,

ε

, x_m) $\longrightarrow$ (p_m,

ε

)

δ'

(p_m,

ε

ε

) $\longrightarrow$ (p_m+1, y_n)

δ'

(p_m+1,

ε

ε

) $\longrightarrow$ (p_m+2, y_n-1)

$\vdots$

δ'

(p_m+n-1,

ε

ε

) $\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（1997）．Introduction to the Theory of Computation．PWS Publishing．ISBN 0-534-94728-X． Section 2.2: Pushdown Automata, pp.101–114.

自动机理论: 形式语言和形式文法
乔姆斯基层级	文法	语言	极小自动机
类型 0	无限制	递归可枚举	图灵机
n/a	(无公用名)	递归	判定器
类型 1	上下文有关	上下文有关	线性有界
n/a	附标	附标	嵌套堆栈
n/a	树-邻接	适度上下文有关	嵌入下推
类型 2	上下文无关	上下文无关	非确定下推
n/a	确定上下文无关	确定上下文无关	确定下推
类型 3	正则	正则	有限
每个语言或文法范畴都是其直接上面的范畴的真子集。

分类: 编译原理 | 自动机

See also ebooksgratis.com: no banners, no cookies, totally FREE.

下推自动机

维基百科，自由的百科全书

目录

[编辑] 综述

[编辑] 形式定义

[编辑] 例子

[编辑] 理解计算过程

[编辑] 广义下推自动机(GPDA)

[编辑] 参见

[编辑] 外部链接

[编辑] 参考书目

Views

导航

帮助

搜索

其他语言