DFA 永遠做不到的那一件事
到現在你有兩種方式描述同一個世界。從正規語言那幾階，你信任一台 DFA：一台像旋轉柵門的機器，只記得目前的狀態。從文法那一階，你信任一個 上下文無關文法：一份有限的規則清單，其遞迴（S → a S b、S → ( S )）生成無界、配對的巢狀。本階梯要回答的那個惱人問題是：有沒有一台機器——一個逐步讀取的「讀者」，而非生成器——其原始能力與文法相當？ DFA 在這裡毫無辦法，因為要辨識 a^n b^n，它得記住自己看過多少個 a，而它固定且有限的狀態集合根本裝不下一個無界的計數。
所以解方不是一組更聰明的狀態——沒有任何有限控制器能無界計數。解方是給機器一份額外的記憶體。但要哪一種？一本可任意讀寫的筆記本太多了（那會一路衝過頭，變成一台圖靈機，遠比任何文法都強）。本階梯的驚喜在於：單一一份受到嚴格限制的記憶體，份量恰恰好。那份記憶體就是一個堆疊。
把一疊盤子當記憶體
想像一疊裝在彈簧托盤上的自助餐盤。你永遠只能把盤子放到「最上面」（推入，push），或拿走「最上面」那一個（彈出，pop）——你伸不進中間，也偷看不到底部。這就是作為記憶體的堆疊的全部詞彙，也是下推自動機在有限控制之外唯一多出來的資源。有兩項性質使它的能力份量恰到好處。第一，它是無界的：盤堆可以長到所需的任意高度，所以機器能記住任意大的計數——每個 a 一個盤子，沒有固定上限。第二，它的存取是受限的：任一瞬間只有最上面可見；底下的一切都被鎖住，直到上面的盤子被彈掉為止。
來看它在 a^n b^n（相同數量的 a，接著相同數量的 b）上實際運作的畫面。由左到右讀。每讀到一個 a，就在堆疊上推入一個標記。一旦 b 開始出現，每讀到一個 b，就彈出一個標記。若標記恰好在輸入讀完的同時用盡，代表數量相符——接受；若多剩一個標記，或標記太早用完，就拒絕。堆疊做到了 DFA 做不到的那一件事：它存下了一個無界大小的計數，再成對同步地把它花回去。（你會在本階梯第四篇逐步追蹤這次運行；這裡只要感受它為什麼行得通。）
把機器寫下來：七元組
一旦直覺穩固——有限控制加上一個堆疊——我們就把整台機器精確寫下，就像你當初把 DFA 定下為一個五部分的元組那樣。一台下推自動機（PDA）是一個 七元組 (Q, Σ, Γ, δ, q0, Z0, F)。令人滿意的地方在於：與 DFA 的五個部分相比，PDA 恰好多加了兩項新材料，而且兩者都描述堆疊。新的能力、兩個新零件，僅此而已。
逐一讀這七個部分：Q 是狀態的有限集合（即控制）；Σ（Sigma，輸入字母表）是機器讀取的字母集合；Γ（Gamma，堆疊字母表）是它可推入與彈出的「另一組」有限符號；δ（delta）是轉移規則手冊；q0 是起始狀態；Z0 是開始時就在堆疊上的起始堆疊符號；而 F（Q 的子集）是接受狀態的集合。相較於 DFA，真正新增的兩項是 Γ 與 Z0——堆疊自己的字母表，以及它的起始標記。
堆疊究竟如何移動
DFA 的轉移讀一樣東西並改變狀態。一次 PDA 轉移同時讀三樣東西並做更多事。標準形式是 δ(q, a, X) = 一組由 (p, γ) 對構成的集合：在狀態 q、讀輸入符號 a、堆疊頂端為 X 時，機器可以移動到狀態 p，並把彈出的 X 替換成堆疊符號串 γ（gamma）。所以每個 PDA 動作都是「彈出頂端、再推入一串」，而這條統一的規則涵蓋了全部三種情況：
- 彈出 X、推入一個較長的串（例如推入 X X）——淨推入，堆疊長高一層。這就是每個 a 如何疊上另一個計數標記。
- 彈出 X、推入空字串 ε（epsilon，意即什麼都不推）——純彈出，堆疊縮小一層。這就是每個 b 如何抵銷一個標記。
- 彈出 X、再把 X 推回（同一個單一符號）——高度不變，但機器仍可改變狀態。一種「偷看後留在原地」。
有兩個細節容易漏看。第一，輸入符號 a 可以是 ε——一次 epsilon-移動 讓機器不消耗任何輸入就動作，純粹憑藉它的狀態與堆疊頂端（很適合收尾步驟與切換模式）。第二，這個配對計數的把戲揭示了為什麼 PDA 的快照需要第三個成分。有限自動機的整個處境是 (狀態, 剩餘輸入)；PDA 需要 (狀態, 剩餘輸入, 堆疊內容)——而這張快照稱為瞬間描述（ID）。由於堆疊可以無界地高，PDA 有無限多個可能的 ID，這正是為什麼它能計數，而格局數有限的 DFA 卻不能。
A PDA for a^n b^n (input alphabet Sigma = {a, b}; stack alphabet Gamma = {X, Z0})
delta(q0, a, Z0) = { (q0, X Z0) } in q0, read a, top Z0: push first X above Z0
delta(q0, a, X) = { (q0, X X) } in q0, read a, top X: push another X (grow)
delta(q0, b, X) = { (q1, epsilon) } first b: pop an X, switch to q1
delta(q1, b, X) = { (q1, epsilon) } in q1, read b, top X: pop an X (shrink)
delta(q1, eps, Z0) = { (qf, Z0) } no input left, top Z0: jump to accept state qf
Run on aabb, ID = (state, remaining input, stack top..bottom):
(q0, aabb, Z0) |- (q0, abb, X Z0) push X (read a)
|- (q0, bb, X X Z0) push X (read a)
|- (q1, b, X Z0) pop X (read b, switch to q1)
|- (q1, eps, Z0) pop X (read b)
|- (qf, eps, Z0) accept (epsilon-move, stack back to Z0)兩個驚喜：與文法匹敵，以及確定性的代價
現在來看招牌回報。PDA 是文法的機器對應物，且是在最鋒利的意義上：一個語言能由某個上下文無關文法生成，若且唯若它能由某台下推自動機辨識。這就是 CFG–PDA 等價，是下方那幾階「正規表示式等於有限自動機」在下推層級的回響。兩個方向都以明確的構造證明——把任何文法轉成一台在堆疊上模擬推導的 PDA，再把任何 PDA 轉回一個文法——所以 PDA 辨識的恰好是上下文無關語言，不多也不少。（本階梯第三篇會建構這兩個翻譯。）
但在那個「某」字裡，藏著第二個、更深的驚喜。一般的 PDA 是非確定性的：在某一時刻它可能有好幾個合法動作，而只要「某一」串選擇導向接受，它就接受——把它想成複製自己以嘗試每條分支，或一位幸運的猜測者，只要存在致勝路徑就總能挑中。（和 NFA 一樣，這是一個精確的數學裝置，不是隨機、也不是一台真的平行機器。）對某些語言，這個猜測無可避免：要辨識像 abba 這種偶數長度迴文，PDA 必須推入前半段、並在開始比對前猜中點在哪——而那個中點無法事先計算出來。
這裡正是下推自動機以一種真正讓所有人驚訝的方式，與有限自動機分道揚鑣之處。對有限自動機，非確定性是免費的：每個 NFA 都有等價的 DFA，所以猜測只換來簡潔。對下推自動機，這是錯的。一台確定型 PDA（每一步只有一個合法動作）辨識的語言嚴格地少於非確定型——偶數長度迴文是上下文無關的，卻沒有任何確定型 PDA 能辨識它，而 a^n b^n「是」確定型的（輸入本身就標示出何時該從推入切換為彈出）。DPDA 能處理的語言稱為確定型上下文無關語言，是所有上下文無關語言的一個真子集。這個不對稱不是腳註：它正是為什麼真實的編譯器把自己的文法限制在確定型那一類（LL、LR），好讓剖析器能向前線性時間運行、且不回溯。本階梯第五篇將專門討論它。