下推自动机

在自動機理論中，**下推自動機**（英語：Pushdown automaton）是使用了包含數據的棧的有限自動機。

## 綜述

下推自動機比有限狀態自動機複雜：除了有限狀態組成部分外，還包括一個長度不受限制的棧；下推自動機的狀態遷移不但要參考有限狀態部分，也要參照棧當前的狀態；狀態遷移不但包括有限狀態的變遷，還包括一個棧的出棧或入棧過程。下推自動機可以形象的理解為，藉由加上讀取一個容量無限棧的能力，擴充一個能做 $\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_{1}w_{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^{n}1^{n}|n\geq 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 $\geq $ 0, y1y2...yn $\in \Gamma ^{*}$ , n $\geq $ 0。

構造 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)

## 參見

* 確定下推自動機
* 有限狀態自動機
* 上下文無關文法

## 外部連結

* 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.