PDA 如何接受：以終止狀態或以空堆疊

運行中機器的一張快照

在上一篇你打造了機器本身：一個有限控制加上單一堆疊，寫成那個七元組。但「擁有一輛車的零件」和「描述它行進到一半的樣子」是兩回事。要精確說出一台 PDA 在某一瞬間正在「做什麼」，你需要一張快照——也就是你得寫在便利貼上、足以暫停運行並稍後從同一處繼續的一切。對有限自動機來說那張便利貼很小：只要當前狀態，以及你還沒讀到的輸入。PDA 需要多一樣東西，因為它多長了一塊記憶體。

那張快照叫做瞬間描述（instantaneous description），簡稱 ID（有些書稱它為格局或組態）。一個瞬間描述是一個三元組：當前狀態、仍待讀取的剩餘輸入，以及由上而下的整個堆疊內容。例如 (q1, bb, X X Z0) 讀作：控制處於狀態 q1，還剩「bb」待讀，而堆疊由上而下是 X、再一個 X、最底是 Z0。把它和有限自動機的（狀態, 剩餘輸入）那一對相比：唯一多出來的就是堆疊，而這恰好就是把機器從正規能力提升到上下文無關能力的那項額外資源。

任何運行的起始快照形狀總是相同：(q0, w, Z0)——在起始狀態 q0 開機，整個輸入 w 等著被讀，而堆疊上只有起始堆疊符號 Z0，也就是那張貼在盤堆最底、寫著「這是地板」的貼紙。這裡有個悄悄重要的後果：由於堆疊部分可以長到任意高，一台 PDA 有「無限多」種可能的 ID。DFA 永遠只有有限多種處境（每個狀態各一種，再乘上你在輸入裡的位置），而這種有限性正是它的記憶體天花板。PDA 那個無界的堆疊正是打破天花板、讓它無限制計數的關鍵。

向前推進：移動關係

快照是一張靜照；一段計算則是一部影片。把一格變成下一格的規則就是移動關係，以一個旋轉柵門符號書寫、常打成 |-，唸作「產生（yields）」或「移動到」。移動關係只是規定：根據你上一篇認識的轉移函數 delta，哪個 ID 能合法地接在哪個之後。單一步驟（至多）消耗一個輸入符號、改變狀態、改寫堆疊頂端——其餘的一切都不動。

把它攤開：若 delta(q, a, X) 允許動作 (p, gamma)，則 (q, a w, X b) |- (p, w, gamma b)。慢慢讀。機器原本在狀態 q，下一個輸入字母是 a，X 壓在堆疊最上面（其餘堆疊 b 在它下方，其餘輸入 w 在 a 之後）。這一步之後，它處於狀態 p，a 已被吃掉所以只剩 w，而頂端的 X 被替換成字串 gamma——壓在底下的那部分 b 完全沒被碰到。一次 epsilon-移動做的事完全一樣，但不消耗任何輸入字母，純粹憑藉狀態與堆疊頂端就移動。注意「把頂端替換成 gamma」涵蓋了所有情況：gamma = epsilon 是純彈出（堆疊縮小）、gamma = X 是偷看後留在原地、而更長的 gamma 是淨推入。

第一種方式：以終止狀態接受

現在來到核心問題：機器何時算「接受」了？第一個答案，正是你早已從有限自動機那裡信任的那一個——看控制停在哪裡。在以終止狀態接受之下，PDA 接受一個輸入字串的條件是：讀完最後一個符號後，有限控制停在指定的接受狀態集合 F 之中。堆疊上剩下什麼雜物一律忽略；我們只檢查控制。這恰好推廣了 DFA：DFA 看它停在哪個狀態來接受，這台 PDA 也一樣——堆疊只是一路上做了記帳之責。

用移動關係釘住它：機器以終止狀態接受輸入 w 的條件是，起始 ID (q0, w, Z0) 在零步或多步內產生某個 ID (p, epsilon, gamma)，其中 p ∈ F。逐部分讀那個目標三元組。中間那格的 epsilon 表示所有輸入已被消耗；p ∈ F 表示控制落在某個接受狀態；而 gamma 是堆疊恰好剩下的任何東西——它的內容完全無關緊要。並記得機器是非確定性的，所以「接受」意味那棵複製樹中「某一條」分支在輸入讀完時抵達一個接受的 ID。哪怕只有一條成功路徑就夠了；失敗的複製體都被原諒。

第二種方式：以空堆疊接受

第二個答案完全丟開控制狀態，改而盯著堆疊。在以空堆疊接受之下，PDA 接受一個輸入的條件是：讀完它的全部之後，機器把堆疊彈到一乾二淨——連地板符號 Z0 本身也彈掉。它最後停在哪個狀態無關緊要；「清空堆疊就是」成功的信號。形式上，(q0, w, Z0) 產生某個 ID (p, epsilon, epsilon)：所有輸入消失（第二個 epsilon）、堆疊清空到一無所有（第三個 epsilon）、狀態 p 被忽略。

這作為停止規則之所以如此乾淨，有個小小的機械原因。一旦堆疊真正為空，機器就「卡住」了：每個 PDA 動作都得先有一個頂端符號可彈出，而此刻一個也沒有，於是再也沒有任何轉移能觸發。因此清空堆疊是不可逆的、天生就是終結性的——這恰是你想要的接受條件性質。這也正是 Z0 不白拿薪水之處：只要那張地板貼紙還在底下，堆疊在運行中途就絕不會意外「為空」，所以清空它是個刻意、有意義、專留給終點線的動作。

Two runs of an a^n b^n machine on input  aabb
(top of stack is written on the LEFT)

  start:  (q0, aabb, Z0)
          |-  (q0, abb,  X Z0)     read a, push X
          |-  (q0, bb,   X X Z0)   read a, push X
          |-  (q1, b,    X Z0)     read b, pop X
          |-  (q1, eps,  Z0)       read b, pop X

Final-state mode:  one more eps-move  (q1, eps, Z0) |- (qf, eps, Z0),
                   qf in F, input empty  -> ACCEPT  (stack still has Z0)

Empty-stack mode:  one more eps-move  (q1, eps, Z0) |- (q1, eps, eps),
                   input empty, stack empty  -> ACCEPT  (state ignored)

同一段運行，兩條終點線：終止狀態模式檢查控制、忽略剩下的 Z0；空堆疊模式連 Z0 也彈掉、忽略狀態。

為什麼兩種模式一致

兩個「接受」的定義引出一個明顯的疑慮：它們抓到的是同一批機器嗎？會不會有些語言只能靠檢查狀態抓到，另一些只能靠清空堆疊抓到？令人安心的定理是：兩者等價。兩種接受模式的等價說：以終止狀態接受的語言類別，「恰好」就是以空堆疊接受的語言類別——而且兩個類別都正是上下文無關語言。模式的選擇是方便與否的問題，從不是能力的問題。

證明是一對小小的「機器轉機器」變換，而兩者的訣竅都是一個別人碰不到的全新底部標記。要把以空堆疊接受者轉成以終止狀態接受者，在原本的 Z0 底下塞一個全新的符號 Z'、再加一個全新的接受狀態 qf；每當舊機器會把堆疊清空到 Z' 時，新機器改花一次 epsilon-移動跳進 qf。反過來，當一台以終止狀態接受的機器抵達接受狀態時，讓它跑一段由 epsilon-移動構成的清理程序，把一切都彈光——而那個額外的底部標記則防止堆疊在正常運行中意外清空。

從一台以空堆疊接受、辨識語言 L 的 PDA P 出發。
建造 P'，在 Z0 底下放一個新的底部符號 Z'，加一個新的起始狀態先把 Z0 推到 Z' 之上，再加一個新接受狀態 qf。
讓 P' 一步步模擬 P；每當 P 會彈到露出 Z' 時，P' 改以一次 epsilon-移動進入 qf。
於是 P' 以終止狀態接受的字串，恰好就是 P 以空堆疊接受的字串——所以 L 也能被終止狀態模式捕捉。

這替後面鋪了什麼路

退一步看看我們現在擁有什麼：一張精確的快照（ID）、一個精確的單步概念（移動關係），以及兩個精確、可證等價的成功定義。這就是「運行」一台 PDA 的完整文法，也是這一階每條定理都會說的語言。當下一篇證明下推自動機恰好辨識上下文無關語言——也就是上下文無關文法所生成的同一類別時，那個證明會字面上建出一台在堆疊上模擬推導、並在模擬一成功就以空堆疊接受的 PDA。

有一個要帶往後面的警告，因為它是這一階等著你的最深層意外。上面的一切都假設 PDA 可以猜——那就是它的非確定性，那種讓「某一條」分支成功的複製。對有限自動機而言，那種猜測是免費的：每個 NFA 都有等價的 DFA。對下推自動機而言，它斷然「不」免費。確定型 PDA 每張快照至多只准一個動作，辨識的語言類別嚴格地較小。終止狀態對上空堆疊，是說「是」的兩種對等方式；確定型對上非確定型，則是能力上一道真實的鴻溝。第五篇會回到正是這道鴻溝，而它就是真實編譯器限制其文法的原因。