茶年 · 中文维基百科

下推自动机

Wikipedia · 2025-10-19 维基百科 👁 1 阅读

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

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

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

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

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

下推自动机作为一个形式系统最早于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) 写 \delta(q1, \epsilon, \epsilon) \rightarrow (q2, $) 来表示 (q2, $) \in \delta(q1, \epsilon, \epsilon)

:: s0 = \epsilon, s1 = $, t = \epsilon, a = \epsilon, b = $

:: 设置 r0 = q2

: (ii) \delta(r0, 0, \epsilon) = \delta(q2, 0, \epsilon) \rightarrow (q2, 0)

:: s1 = $, a = \epsilon, t = $, b = 0, s2 = 0$

:: 设置 r1 = q2

: (iii) \delta(r1, 0, \epsilon) = \delta(q2, 0, \epsilon) \rightarrow (q2, 0)

:: s2 = 0$, a = \epsilon, t = 0$, b = 0, s3 = 00$

:: 设置 r2 = q2

: (iv) \delta(r2, 1, 0) = \delta(q2, 1, 0) \rightarrow (q3, \epsilon)

:: s3 = 00$, a = 0, t = 0$, b = \epsilon, s4 = 0$

:: 设置 r3 = q3

: (v) \delta(r3, 1, 0) = \delta(q3, 1, 0) \rightarrow (q3, \epsilon)

:: s4 = 0$, a = 0, t = $, b = \epsilon, s5 = $

: (vi) \delta(q3, \epsilon, $) \rightarrow (q4, \epsilon)

:: s5 = $, a = $, t = \epsilon, b = \epsilon, s6 = \epsilon

:: 设置 r4 = q4

: 因为 q4 是接受状态，0011 被接受。

: 作为总结，计算路径 = (q1, q2, q2, q2, q3, q3, q4)

: 而 (r0, r1, r2, r3, r4) = (q2, q2, q2, q3, q4)

(b) 输入字符串 = 001

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

: (v) \delta(r3, \epsilon, a) = \delta(q3, \epsilon, a)

:: 因为 s4 = 0$，要么 a = \epsilon 要么 a = 0

:: 在任何一种情况下，\delta(q3, \epsilon, a) = \varnothing

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

(c) 输入字符串 = \epsilon

: 设置 r0 = q1, r1 = q1

: \delta(r0, \epsilon, \epsilon) \rightarrow (q1, \epsilon)

: 因为 q1 是接受状态，\epsilon 被接受。

广义下推自动机(GPDA)
GPDA 是在一个步骤内写入整个字符串到栈上或从栈上去除整个字符串的 PDA。

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

:这里的 Q, \Sigma\,, \Gamma\,, q0 和 F 的定义同于 PDA。

:\,\delta: Q \times \Sigma_{\epsilon} \times \Gamma^{} \longrightarrow \mathcal{P}( Q \times \Gamma^{} ) 是转移函数。

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

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

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

设 \delta(q1, w, x1x2...xm) \longrightarrow (q2, y1y2...yn) 是 GPDA 的转移。

这里的 q1, q2 \in Q, w \in\Sigma_{\epsilon}\,, x1x2...xm \in\Gamma^{}, m\geq0, y1y2...yn \in\Gamma^{}, n\geq0。

构造 PDA 的下列转移：

::\delta^{'}(q1, w, x1) \longrightarrow (p1, \epsilon)

::\delta^{'}(p1, \epsilon, x2) \longrightarrow (p2, \epsilon)

::::\vdots

::\delta^{'}(pm-1, \epsilon, xm) \longrightarrow (pm, \epsilon)

::\delta^{'}(pm, \epsilon, \epsilon ) \longrightarrow (pm+1, yn)

::\delta^{'}(pm+1, \epsilon, \epsilon ) \longrightarrow (pm+2, yn-1)

::::\vdots

::\delta^{'}(pm+n-1, \epsilon, \epsilon ) \longrightarrow (q2, y1)

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

外部链接

参考书目

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

评论 (0)

  • 还没有评论，来抢沙发吧。