下推自動機（pushdown automaton）

有限自動機就像一道旋轉柵門，只記得自己處在哪個狀態——而這正是它致命的弱點：狀態數量固定，它無法無界地計數，所以無法判斷一個字串裡 a 和 b 是否一樣多。補救之道雖小卻有力：給機器一項額外資源——一個堆疊（stack），就像一疊便條，你永遠只能查看、放上或拿走「最上面」那一張。下推自動機正是「有限狀態控制加上單一堆疊」，這一項增添就把它從正規語言一路提升到上下文無關語言。

看它實際運作：要辨識語言 a^n b^n（相同數量的 a 接著相同數量的 b），PDA 由左到右讀輸入。每讀到一個 a，就在堆疊上推入（push）一個標記；等 b 開始出現後，每讀到一個 b，就彈出（pop）一個標記。如果輸入結束時堆疊恰好清空，代表數量相符，機器就接受；否則拒絕。這個堆疊就是它「無界但受限存取」的記憶體：深度無限，但永遠只能碰最上面。這正是記憶體有限的有限自動機永遠做不到的計數。

下推自動機之所以重要，是因為它是上下文無關文法的「機器」對應物：兩者描述的語言類別恰好相同，也就是上下文無關語言；正如有限自動機與正規表示式描述正規語言一般。它是剖析器背後的理論、遞迴背後的資料結構，也是為什麼「待處理的函數呼叫堆」或「尚未閉合的括號」自然就以堆疊建模的原因。先講一個老實的提醒：PDA 一般而言是非確定性的，而且和有限自動機不同，它的確定型版本嚴格地較弱——這個差異對真實的編譯器影響極大。