下推自動機

在自動機理論中，下推自動機是使用了包含資料的棧的有限自動機。綜述.下推自動機比有限狀態自動機複雜：除了有限狀態組成部分外，還包括一個長度不受限制的棧；下推自動機的狀態遷移不但要參考有限狀態部分，也要參照棧當前的狀態；狀態遷移不但包括有限狀態的變遷，還包括一個棧的出棧或入棧過程。下推自動機可以形象的理解為，藉由加上讀取一個容量無限棧的能力，擴充一個能做formula_1-轉移的非確定有限狀態自動機。下推自動機存在“確定”與“非確定”兩種形式，兩者並不等價。每一個下推自動機都接受一個形式語言。被“非確定下推自動機”接受的語言是上下文無關語言。如果我們把下推自動機擴充套件，允許一個有限狀態自動機存取兩個棧，我們得到一個能力更強的自動機，這個自動機與圖靈機等價。下推自動機作為一個形式系統最早於1961年出現在 Oettinger 的論文中。它與上下文無關文法的等價性是由喬姆斯基於1962年發現的。形式定義.PDA 形式定義為 6-元組：formula_2這裡的計算定義 1對於任何 PDA formula_2，計算路徑是一個有序的-元組 formula_13，這裡的 formula_14，它滿足如下條件：(i) formula_15 對於 i = 0, 1, 2..., n-1,這裡的 formula_16(ii) formula_17 使得formula_18在直覺上，PDA 在計算過程中任何一點上都面對著多種可能性，從棧頂讀一個符號並把它替代為另一個符號，從棧頂讀一個符號並刪除它而不替換，不從棧頂讀任何符號但壓入另一個符號進去，或什麼都不做。所有這些都同時由等式 formula_19 和 formula_20 來支配。formula_21 是緊接在第 i+1 次轉移移動之前的棧內容，而 formula_22 是要從棧頂去除的符號。formula_23 是緊接在第 i+1 次轉移移動之後棧內容，而 formula_24 是在第 i+1 次轉移移動期間要增加到棧上的符號。formula_22 和 formula_24 二者都可以 formula_27。如果 formula_28 而 formula_29，則 PDA 從棧讀一個符號並把它替代為另一個符號。如果 formula_28 而 formula_31，則 PDA 從棧讀一個符號並刪除它而不替換。如果 formula_32 而 formula_29，則 PDA 簡單的增加一個符號到棧上。如果 formula_32 而 formula_31，則 PDA 保持棧不變動。注意當 n=0 時，計算路徑就是單元素集合 formula_36。計算定義 2對於任何輸入 formula_37，M 接受 w，如果存在計算路徑 formula_38 和有限序列 formula_39，使得(i) 對於每個 i = 0, 1, 2...m，formula_40 都在計算路徑上。就是說formula_41 這裡的 formula_42 使得 formula_43(ii) formula_44 對於每個 i = 0, 1, 2...m-1。這裡的 formula_45 和 formula_46 定義同於計算定義 1。(iii) formula_47，如果 formula_48這裡的 formula_49 和 formula_50 定義同於計算定義 1。(iv) formula_51 且 formula_52注意上述定義不提供測試空棧的機制。要這麼做你需要在所有計算開始前在棧上寫一個特殊符號，使得 PDA 可以在檢測到這個符號的時候有效的識別出棧已經空了。形式的說，實現它可透過介入轉移 formula_53這裡的 $ 是特殊符號。例子.下面是識別語言 formula_54 的 PDA 的形式描述：formula_55理解計算過程.下面展示上述 PDA 如何計算不同的輸入字串。(a) 輸入字串 = 0011(i) 寫 formula_66(q1, formula_1, formula_1) formula_69 (q2, $) 來表示 (q2, $) formula_70 formula_66(q1, formula_1, formula_1)s0 = formula_1, s1 = $, t = formula_1, a = formula_1, b = $設定 r0 = q2(ii) formula_66(r0, 0, formula_1) = formula_66(q2, 0, formula_1) formula_69 (q2, 0)s1 = $, a = formula_1, t = $, b = 0, s2 = 0$設定 r1 = q2(iii) formula_66(r1, 0, formula_1) = formula_66(q2, 0, formula_1) formula_69 (q2, 0)s2 = 0$, a = formula_1, t = 0$, b = 0, s3 = 00$設定 r2 = q2(iv) formula_66(r2, 1, 0) = formula_66(q2, 1, 0) formula_69 (q3, formula_1)s3 = 00$, a = 0, t = 0$, b = formula_1, s4 = 0$設定 r3 = q3(v) formula_66(r3, 1, 0) = formula_66(q3, 1, 0) formula_69 (q3, formula_1)s4 = 0$, a = 0, t = $, b = formula_1, s5 = $(vi) formula_66(q3, formula_1, $) formula_69 (q4, formula_1)s5 = $, a = $, t = formula_1, b = formula_1, s6 = formula_1設定 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) formula_66(r3, formula_1, a) = formula_66(q3, formula_1, a)因為 s4 = 0$，要麼 a = formula_1 要麼 a = 0在任何一種情況下，formula_66(q3, formula_1, a) = formula_113因此計算在 r3 = q3 進入死衚衕，這不是接受狀態。所以 001 被拒絕。(c) 輸入字串 = formula_1設定 r0 = q1, r1 = q1formula_66(r0, formula_1, formula_1) formula_69 (q1, formula_1)因為 q1 是接受狀態，formula_1 被接受。廣義下推自動機(GPDA).GPDA 是在一個步驟內寫入整個字串到棧上或從棧上去除整個字串的 PDA。GPDA 形式定義為 6-元組 formula_2這裡的 Q, formula_122, formula_123, q0 和 F 的定義同於 PDA。formula_6: formula_125 是轉移函式。GPDA 的計算規則同於 PDA，除了 ai+1 和 bi+1 現在是字串而不是符號之外。GPDA 和 PDA 是等價的，如果一個語言可被一個 PDA 識別，它也可被一個 GPDA 識別，反之亦然。可以使用下列模擬公式化對 GPDA 和 PDA 的等價性的一個分析式證明：設 formula_66(q1, w, x1x2...xm) formula_127 (q2, y1y2...yn) 是 GPDA 的轉移。這裡的 q1, q2 formula_70 Q, w formula_129, x1x2...xm formula_130, mformula_1310, y1y2...yn formula_130, nformula_1310。構造 PDA 的下列轉移：formula_134(q1, w, x1) formula_127 (p1, formula_1)formula_134(p1, formula_1, x2) formula_127 (p2, formula_1)formula_141formula_134(pm-1, formula_1, xm) formula_127 (pm, formula_1)formula_134(pm, formula_1, formula_1 ) formula_127 (pm+1, yn)formula_134(pm+1, formula_1, formula_1 ) formula_127 (pm+2, yn-1)formula_141formula_134(pm+n-1, formula_1, formula_1 ) formula_127 (q2, y1)