綜述

下推自動機比有限狀態自動機復雜：除了有限狀態組成部分外，還包括一個長度不受限制的棧；下推自動機的狀態遷移不但要參考有限狀態部分，也要參照棧當前的狀態；狀態遷移不但包括有限狀態的變遷，還包括一個棧的出棧或入棧過程。下推自動機可以形象的理解為，借由加上讀取一個容量無限堆棧的能力，擴充一個能做ε-轉移的非確定有限狀態自動機。

下推自動機存在“確定”與“非確定”兩種形式，兩者并不等價。（對有限狀態自動機兩者是等價的）

每一個下推自動機都接受一個形式語言。被“非確定下推自動機”接受的語言是上下文無關語言。

如果我們把下推自動機擴展，允許一個有限狀態自動機存取兩個棧，我們得到一個能力更強的自動機，這個自動機與圖靈機等價。

下推自動機作為一個形式系統最早于1961年出現在 Oettinger 的論文中。它與上下文無關文法的等價性是由喬姆斯基于1962年發現的。

[編輯] 形式定義

PDA 形式定義為 6-元組:

這里的

• 是狀態的有限集合
• 是輸入字母表的有限集合
• 是棧字母表的有限集合
• : 是轉移函數
• q₀ 是“開始狀態”
• 是“接受狀態”的集合
• 
• 

計算定義 1

對于任何 PDA ，計算路徑是一個有序的(n+1)-元組 ，這里的 ，它滿足如下條件:

(i) 對于 i = 0, 1, 2,......, n-1,

這里的

(ii) 使得

在直覺上，PDA 在計算過程中任何一點上都面對著多種可能性，從棧頂讀一個符號并把它替代為另一個符號，從棧頂讀一個符號并刪除它而不替換，不從棧頂讀任何符號但壓入另一個符號進去，或什么都不做。所有這些都同時由等式 和 來支配。 是緊接在第 i+1 次轉移移動之前的棧內容，而 是要從棧頂去除的符號。 是緊接在第 i+1 次轉移移動之后棧內容，而 是在第 i+1 次轉移移動期間要增加到棧上的符號。

和 二者都可以 。

如果 而 ，則 PDA 從棧讀一個符號并把它替代為另一個符號。

如果 而 ，則 PDA 從棧讀一個符號并刪除它而不替換。

如果 而 ，則 PDA 簡單的增加一個符號到棧上。

如果 而 ，則 PDA 保持棧不變動。

注意當 n=0 時，計算路徑就是單元素集合 。

計算定義 2

對于任何輸入 ，M 接受 w，如果存在計算路徑 和有限序列 ，使得

(i) 對于每個 i = 0, 1, 2,...m， 都在計算路徑上。就是說

這里的 使得

(ii) 對于每個 i = 0, 1, 2,...m-1。

這里的 和 定義同于計算定義 1。

(iii) ，如果

這里的 和 定義同于計算定義 1。

(iv) 且

注意上述定義不提供測試空棧的機制。要這么做你需要在所有計算開始前在棧上寫一個特殊符號，使得 PDA 可以在檢測到這個符號的時候有效的識別出棧已經空了。形式的說，實現它可通過介入轉移 這里的 $ 是特殊符號。

[編輯] 例子

下面是識別語言 的 PDA 的形式描述:

• 

• 

• 

• 

• 

• 

• 

• 

• 

• 對于任何其他狀態、輸入和棧符號的值。

[編輯] 理解計算過程

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

(a) 輸入字符串 = 0011

(i) 寫 δ(q₁, ε, ε) (q₂, $) 來表示 (q₂, $) δ(q₁, ε, ε)

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

設置 r₀ = q₂

(ii) δ(r₀, 0, ε) = δ(q₂, 0, ε) (q₂, 0)

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

設置 r₁ = q₂

(iii) δ(r₁, 0, ε) = δ(q₂, 0, ε) (q₂, 0)

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

設置 r₂ = q₂

(iv) δ(r₂, 1, 0) = δ(q₂, 1, 0) (q₃, ε)

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

設置 r₃ = q₃

(v) δ(r₃, 1, 0) = δ(q₃, 1, 0) (q₃, ε)

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

(vi) δ(q₃, ε, $) (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) =

因此計算在 r₃ = q₃ 進入死胡同，這不是接受狀態。所以 001 被拒絕。

(c) 輸入字符串 = ε

設置 r₀ = q₁, r₁ = q₁

δ(r₀, ε, ε) (q₁, ε)

因為 q₁ 是接受狀態，ε 被接受。

[編輯] 廣義下推自動機(GPDA)

GPDA 是在一個步驟內寫入整個字符串到棧上或從棧上去除整個字符串的 PDA。

GPDA 形式定義為 6-元組

這里的 Q, , , q₀ 和 F 的定義同于 PDA。

: 是轉移函數。

GPDA 的計算規則同于 PDA，除了 a_i+1 和 b_i+1 現在是字符串而不是符號之外。

GPDA 和 PDA 是等價的，如果一個語言可被一個 PDA 識別，它也可被一個 GPDA 識別，反之亦然。

可以使用下列模擬公式化對 GPDA 和 PDA 的等價性的一個分析式證明:

設 δ(q₁, w, x₁x₂...x_m) (q₂, y₁y₂...y_n) 是 GPDA 的轉移。

這里的 q₁, q₂ Q, w , x₁x₂...x_m , m0, y₁y₂...y_n , n0。

構造 PDA 的下列轉移:

δ^'(q₁, w, x₁) (p₁, ε)

δ^'(p₁, ε, x₂) (p₂, ε)

δ^'(p_m-1, ε, x_m) (p_m, ε)

δ^'(p_m, ε, ε ) (p_m+1, y_n)

δ^'(p_m+1, ε, ε ) (p_m+2, y_n-1)

δ^'(p_m+n-1, ε, ε ) (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.

取自"