woaidongmao

文章均收錄自他人博客，但不喜標題前加-[轉貼]，因其丑陋，見諒！~

隨筆 - 1469, 文章 - 0, 評論 - 661, 引用 - 0

數據加載中……

維基百科----下推自動機

綜述

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

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

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

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

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

[編輯] 形式定義

PDA 形式定義為 6-元組:

$clip_image001$ 這里的

$clip_image002$ 是狀態的有限集合
$clip_image003$ 是輸入字母表的有限集合
$clip_image004$ 是棧字母表的有限集合
$clip_image005$ : $clip_image006$ 是轉移函數
$q$ $0$ 是“開始狀態”
$clip_image007$ 是“接受狀態”的集合
$clip_image008$
$clip_image009$

計算定義 1

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

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

這里的 $clip_image013$

(ii) $clip_image014$ 使得

$clip_image015$

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

$clip_image019$ 和 $clip_image021$ 二者都可以 $clip_image022$ 。

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

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

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

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

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

計算定義 2

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

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

$clip_image032$ 這里的 $clip_image033$ 使得 $clip_image034$

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

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

(iii) $clip_image038$ ，如果 $clip_image039$

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

(iv) $clip_image042$ 且 $clip_image043$

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

[編輯] 例子

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

$clip_image046$

$clip_image047$

$clip_image048$

$clip_image049$

$clip_image050$

$clip_image051$

$clip_image052$

$clip_image053$

$clip_image054$

$clip_image055$

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

[編輯] 理解計算過程

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

(a) 輸入字符串 = 0011

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

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

設置 r₀ = q₂

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

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

設置 r₁ = q₂

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

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

設置 r₂ = q₂

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

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

設置 r₃ = q₃

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

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

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

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

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

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

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

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

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

GPDA 形式定義為 6-元組 $clip_image001$

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

$clip_image005$ : $clip_image062$ 是轉移函數。

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

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

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

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

這里的 q₁, q₂ $clip_image058$ Q, w $clip_image064$ , x₁x₂...x_m $clip_image065$ , m $clip_image066$ 0, y₁y₂...y_n $clip_image065$ , n $clip_image066$ 0。

構造 PDA 的下列轉移:

$δ'$ (q₁, w, x₁) $clip_image063$ (p₁, $ε$ )

$δ'$ (p₁, $ε$ , x₂) $clip_image063$ (p₂, $ε$ )

$clip_image067$

$δ'$ (p_m-1, $ε$ , x_m) $clip_image063$ (p_m, $ε$ )

$δ'$ (p_m, $ε$ , $ε$ ) $clip_image063$ (p_m+1, y_n)

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

$clip_image067$

$δ'$ (p_m+n-1, $ε$ , $ε$ ) $clip_image063$ (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	正則	正則	有限
每個語言或文法范疇都是其直接上面的范疇的真子集。

取自"

posted on 2008-12-30 10:50 肥仔閱讀(1130) 評論(0) 編輯收藏引用所屬分類: 狀態機 & 自動機 & 形式語言

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: 自動機，善用離開事件 C語言詳解 - 表達式和語句棧的應用-表達式求值（后綴式）編譯原理實驗：后綴式求值（c++） FIRST集和FOLLOW集我們能不能說不符合LR(1)的文法等價于二義文法？用C++編寫簡單繪圖語言的語法分析器并行狀態與串行狀態的等價性基于有限狀態機的工控系統軟件設計以基本模型為胎，添加約束，從簡到繁，可以構造精確的系統模型

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

woaidongmao

維基百科----下推自動機

綜述

[編輯] 形式定義

[編輯] 例子

[編輯] 理解計算過程

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

[編輯] 參見

[編輯] 外部鏈接

[編輯] 參考書目

導航

常用鏈接

留言簿(10)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜