下推自動機

在自動機理論中，下推自動機（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_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$\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