在 a^n b^n 上追蹤一台下推自動機

為什麼這一族字串值得寫一整篇

回到正規語言那一階梯，a^n b^n——若干個 a，後接恰好同樣多個 b——正是有限記憶應付不了的那隻金絲雀。幫浦引理證明了這件事：一台 DFA 有固定且有限多個狀態，所以一旦 n 長過那個數目，它就必定要重複用到某個狀態，因而失去對計數的掌握。地球上沒有任何有限自動機能辨識 a^n b^n。那唯一的失敗，正是這一階梯存在的全部理由；而 a^n b^n 是觀看一台下推自動機成功的、再乾淨不過的舞台。

第一篇給出的修法小得令人吃驚：在有限自動機上拴一個裝置——一個堆疊，一疊盤子，你只能碰最上面那一個。控制器仍然只有有限多個狀態，但堆疊是無上限的，所以這台機器得到了一份事先不封頂的記憶。對付 a^n b^n 的計畫幾乎是自己寫出來的：讀 a 的時候，每讀一個 a 就往堆疊上放一個盤子；讀 b 的時候，每讀一個 b 就拿走一個盤子。如果堆疊恰好在輸入用完的同一刻見底，兩個計數就相配了，機器便接受。

把這台機器寫出來

我們來釘住一台對付 a^n b^n 的具體下推自動機，連空字串（n = 0 的情形）一併涵蓋。輸入字母表是 {a, b}。堆疊字母表——堆疊可容納的那一組獨立符號，第一篇強調過它不是跟輸入字母同一組——是 {A, Z}。這裡 A 是我們每讀一個 a 就推上去的盤子，Z 則是一開始就墊在堆疊底的底標記，好讓機器認得出堆疊何時回到了空的狀態。我們用三個控制狀態：q_push（讀 a 們）、q_pop（讀 b 們），以及 q_accept（那個接受狀態）。

每一條轉移都讀三樣東西——當前狀態、一個輸入字母（或 epsilon，意思是什麼都不讀），以及堆疊頂端那一個符號——然後一邊換到新狀態，一邊把那個頂端符號替換成一串（可能為空的）堆疊符號。寫「推 A」意思是把頂端的 X 換成 AX（舊的頂端仍墊在新盤子底下）；「彈出」意思是把頂端符號換成 epsilon（把盤子拿走）；把頂端換成它自己，就是「別動堆疊」。底下這五條規則，就是整支程式。

PDA for a^n b^n  (push a plate per a, pop one per b)

  states:  q_push (start) , q_pop , q_accept (accepting)
  stack symbols:  A (a plate)  ,  Z (bottom marker)
  start stack:  Z      input alphabet:  a , b

  transitions  delta(state, input, top)  ->  (newstate, replacement)

  (1) delta(q_push, a, Z)  -> (q_push,  A Z)     first a: push A onto Z
  (2) delta(q_push, a, A)  -> (q_push,  A A)     later a: push another A
  (3) delta(q_push, eps, Z)-> (q_accept, Z)      no a's at all: accept empty
  (4) delta(q_push, b, A)  -> (q_pop,   eps)     first b: pop one A
  (5) delta(q_pop,  b, A)  -> (q_pop,   eps)     later b: pop another A
  (6) delta(q_pop,  eps,Z) -> (q_accept, Z)      stack empty + done: accept

  'A Z' on the right means: replace top with A then Z  (i.e. push A).
  'eps' on the right means: replace top with nothing    (i.e. pop).

整台機器。規則 (3) 處理 n = 0；規則 (4) 與 (6) 逮住計數見底的那一刻。這裡沒有任何一處讀取「有幾個 A」——它永遠只檢視最上面那一個符號。

一步一步追蹤 aabb

要追蹤一次運行，我們用第二篇的瞬時描述（ID）：一張寫成三元組（狀態、剩餘輸入、堆疊）的快照，其中堆疊以「頂端在左」呈現。從一個 ID 到下一個的一步移動，就是套用一條轉移。整次運行，是一連串 ID 由移動關係串起來的鏈。我們來運行輸入 aabb。一開始我們在 q_push，aabb 全都還沒讀，堆疊上只有底標記 Z。

起始：(q_push, aabb, Z)。堆疊頂端是 Z、下一個字母是 a，所以規則 (1) 觸發：推 A。新 ID：(q_push, abb, AZ)。現在堆疊上有一個盤子。
讀第二個 a。頂端現在是 A、下一個字母是 a，所以規則 (2) 觸發：再推一個 A。新 ID：(q_push, bb, AAZ)。讀了兩個 a、疊了兩個盤子——堆疊的高度就是目前為止看到的 a 的個數。
讀第一個 b。頂端是 A、下一個字母 b，所以規則 (4) 觸發：彈掉一個 A，並切換到 q_pop。新 ID：(q_pop, b, AZ)。至此我們已投入 b 階段；正是這一步在說「a 們結束了」。
讀第二個 b。狀態 q_pop、頂端 A、下一個字母 b，所以規則 (5) 觸發：彈掉最後一個 A。新 ID：(q_pop, , Z)。輸入已耗盡，堆疊只剩底標記 Z——每個盤子付給了一個 a，每次彈出付給了一個 b。
收尾。沒有剩餘輸入、頂端是 Z，所以規則 (6) 在 epsilon 上觸發：不消耗任何東西就移到 q_accept。最終 ID：(q_accept, , Z)。輸入已讀盡、我們在接受狀態，於是 aabb 被接受。a 與 b 的個數恰好相配。

把這條鏈一氣讀完：(q_push, aabb, Z) 通向 (q_push, abb, AZ)、通向 (q_push, bb, AAZ)、通向 (q_pop, b, AZ)、通向 (q_pop, , Z)、通向 (q_accept, , Z)。堆疊升到 AAZ，又對稱地落回 Z。那一升一落，正是該牢記在腦中的畫面：推入築起一座塔，其高度記錄著 a 的個數；彈出則以「每個 b 一個盤子」的步調把它拆掉。當且僅當兩個階段一樣長，這座塔才會在輸入結束的同一刻、恰好回到 Z。

看著它拒絕壞字串

一台正確的機器，不只要接受好字串——它還必須拒絕每一個壞字串，而追蹤那些失敗，正是設計真正驗明正身之處。拿 aab（兩個 a、一個 b）來看。運行是 (q_push, aab, Z) 通向 (q_push, ab, AZ)、通向 (q_push, b, AAZ)，接著規則 (4) 在那個 b 上彈掉一個 A：(q_pop, , AZ)。此刻輸入已空，但堆疊頂端是 A、不是 Z。q_pop 裡沒有任何轉移在頂端為 A 時讀 epsilon，也再沒有輸入可讀——機器卡在一個達不到接受組態的地方。有一個盤子始終沒被付清，所以 aab 被拒絕。那個剩下的 A，就是那個沒配對到的 a。

現在拿次序錯亂的字串 ba。機器從 q_push 起步，第一個字母是 b，頂端是 Z。掃一遍規則：q_push 只知道在 a 上（規則 1、2）或在頂端為 Z 時於 epsilon 上（規則 3）該怎麼做。對 (q_push, b, Z) 根本沒有任何轉移。機器在第一個字母上就卡死、拒絕。這正是機器要投入「階段」的緣由——它在 a 期間推、在 b 期間彈，而一旦開始彈，就沒有路再回到推。「先 a 後 b」的形狀由控制狀態來執行，而「個數相等」由堆疊來執行。兩份工作乾淨地分開了。

兩種接受方式，以及為什麼「猜測」幾乎沒出現

我們這台機器靠抵達 q_accept 來接受——也就是以終態接受。但第二篇介紹了第二種風格，以空堆疊接受：恰在輸入讀完、且堆疊被完全清空時接受，不管狀態如何。我們可以用那種風格重造同一個語言：在末尾連 Z 也彈掉，並拿掉 q_accept。第二篇也告訴過你一個讓人安心的事實：這兩種方式能力相當——任何能用其中一種方式接受的語言，也有某台下推自動機用另一種方式接受它——所以你挑哪一種，純屬方便，從不是能力問題。

這裡有件事，在這個乾淨的例子裡很容易被漏掉。一般的下推自動機是非確定性的：在某個給定組態下，它可能有好幾步合法的移動，而且就像你先前見過的 NFA，只要任何一條分支通向接受，它就接受——就是那幅無害的、把自己複製去試遍每條路的畫面，一個數學裝置，既非隨機亦非免費。然而在我們這台 a^n b^n 機器裡，規則從不重疊：在每個可達組態下，至多只有一條規則適用。我們走運了——這個特定語言可以用確定性的方式做出來。下一篇會說明這份運氣為何會用完，以及為什麼下推自動機的非確定性確實比它的確定性限制更強大——這與有限自動機那種「兩者相等」的情形不同。

退一步，欣賞這個小小的奇蹟。我們在文法那一階梯放進文法 S -> a S b | epsilon 的那份平衡，如今正由一疊盤子來執行：每一次把一個 a 與一個 b 包在內部外頭的規則套用，都對應到「一次推入」配上「稍後一次彈出」。這並非巧合——這是上下文無關語言露出它的兩張臉：那個生成字串的文法，與那個辨識字串的下推自動機。先前那篇談下推自動機與文法的指南，把這份雙向的等價講得精確；而在這裡，你剛剛親眼看著它在一個真實字串上運行了一遍。