記憶體恰好等於狀態數目的機器
到目前為止你已經造出了真正的 DFA：一台接受含偶數個 a 的字串、一台只要看到子字串「abb」就觸發、一台把輸入長度對 3 取餘數，而且你還用乘積構造把多個條件縫在一起。每一台都很巧妙，但它們都共享一個樸實的特徵——一組固定、有限、一次畫好就再也不變的狀態。本篇把這份樸實當真，並追問它的代價。答案正是整個階梯的關鍵句：一台 DFA 的全部記憶體「就是」它目前處在那有限多個狀態中的哪一個，再無其他。
想像地鐵站的旋轉閘門。它不記得今早有多少人通過、不記得你的臉、不記得時間。它只記得唯一一件事：我現在是上鎖還是解鎖？那是兩個狀態。DFA 就是同一類生物，只是狀態多一些——也許五個、也許五百個——但永遠是事先固定好、在它讀入任何一個符號之前就已寫定的數目。當它由左而右掃描輸入時，它對「目前為止看過的一切」所能攜帶向前的全部資訊，都被壓縮成「我現在處於哪個狀態」。如果它有 k 個狀態，它對過去就最多只有 k 種真正不同的記憶。這就是有限記憶體極限，而它不是一個待修的瑕疵——它就是定義本身。
擊垮每一台 DFA 的那個模式
這裡來了那個著名的搗蛋鬼，也就是語言 a^n b^n：若干個 a，然後恰好同樣多的 b。所以「ab」、「aabb」、「aaabbb」都在裡面；但「aab」、「abb」、「aaabb」都在外面。一個六歲小孩就能檢查成員資格：數 a、數 b、看它們是否相等。規則平凡至極。然而沒有任何 DFA——不論它有十個狀態還是一兆個狀態——能識別 a^n b^n。請好好體會這有多奇怪。那台能在十億字元的字串中任何位置揪出「abb」的機器，面對「兩個字母數目相等」卻束手無策。
為什麼？因為識別 a^n b^n 需要記住 n——而 n 可以是任何整數，沒有上限。要知道「aaaaa」應該被恰好五個 b 配對，你就必須以某種方式記下「五」這個計數。但 DFA 只有 k 個狀態，這個數目在它開始運行之前就已釘死。要區分 a、aa、aaa……所有這些前綴並對每一個正確回應，它就需要為任意大的計數各備一份記憶。一個固定有限的狀態袋子，根本裝不下無上限的數目。這句口號精確且值得背下來：DFA 無法無界地計數。 它可以永遠對固定的 k 取餘數計數（那只需 k 個狀態循環使用），但它無法保有一個可能超過任何上限的累計值。
把碰撞逼出來的鴿籠原理
光是揮揮手說「它記不夠多」並不令人滿意；讓我們用鴿籠原理把它釘得滴水不漏——那個樸素的事實：若放進的鴿子比鴿籠多，總有一個籠子塞進兩隻鴿子。為了導出矛盾，假設某台恰有 k 個狀態的 DFA M 確實識別 a^n b^n。餵給它 k+1 個純粹由 a 組成的輸入：空字串、「a」、「aa」，一直到重複 k 次的「a」。讀完這些前綴中的每一個之後，M 會停在某個狀態。前綴有 k+1 個，狀態卻只有 k 個，所以必有兩個不同的前綴——譬如 a^i 與 a^j，其中 i 不等於 j——會讓 M 落到完全相同的狀態。此時 M 真的再也分不出這兩個前綴了；從這個狀態起，無論它讀的是哪一個，未來的行為都一模一樣。
現在把陷阱關上。給這兩者各接上恰好 i 個 b。字串 a^i b^i 在語言裡，必須被接受；但 a^j b^i 不在語言裡（計數不相等），必須被拒絕。然而 M 在讀完 a^i 與讀完 a^j 之後處於相同狀態，所以它對尾巴上那串「b^i」在兩種情況下都做同一件事——要嘛兩個都接受，要嘛兩個都拒絕。這兩個裁決必有一個是錯的。矛盾被逼了出來，所以我們的假設是錯的：沒有任何 k 個狀態的 DFA 能識別 a^n b^n，又因為 k 是任意的，沒有任何 DFA 能做到。注意這個論證的形狀——它是一個反證法，而它的引擎純粹就是鴿籠原理。
M has k states. Feed k+1 prefixes of a's:
prefix: (empty) a aa aaa ... a^k <- k+1 prefixes
state: s0 s1 s2 s3 ... sk <- only k states exist
\ /
PIGEONHOLE: two prefixes share a state
say a^i and a^j (i != j) land in the SAME state q
Now append b^i to each, starting from that shared state q:
a^i b^i -> (same state q) ->[reads b^i]-> verdict V must ACCEPT (in language)
a^j b^i -> (same state q) ->[reads b^i]-> verdict V must REJECT (not in language)
Same start state q, same suffix b^i => same verdict V for both.
But one must be accepted and the other rejected. CONTRADICTION.替這招命名：幫浦引理
那個「兩個前綴相撞」的論證實在太好用了，於是它得到了一個名字和一個可重複套用的形式：正規語言的幫浦引理。它說：對任何正規語言，都存在一個長度 p（幫浦長度，本質上就是狀態的個數），使得每個至少這麼長的字串裡，都含有一個非空的中間區塊，你可以把它重複——「幫浦」——任意多次而仍留在語言裡。這個直覺正是把鴿籠碰撞盛裝打扮：一個夠長的字串必定會重訪某個狀態，而兩次造訪之間的那個迴圈可以走零次、一次、兩次、無限次，每一種都產生被接受的字串。要證明像 a^n b^n 這樣的語言不是正規語言，你就證明這種可幫浦的中段不可能存在，於是這個語言被定罪。
極限在哪裡為真，又在哪裡並非如此
我們很容易得出錯誤的教訓，所以讓我們精確說明這個極限說了什麼、又沒說什麼。這個極限講的是「無界的記憶體」，而不是日常意義上的任何難度。a^n b^n 在計算上平凡至極；障礙純粹在於：配對計數所需的儲存空間會隨輸入增長。相對地，前幾篇導覽裡一個真正的微妙之處原封不動地存活了下來：非確定性「救不了」你。一台 NFA——那個能「自我複製」以同時探索多條路徑的版本——並不比 DFA 更強大；子集構造能把任何 NFA 變回一台 DFA。非確定性只換來簡潔，有時是更小的狀態圖，卻換不來哪怕一個額外的語言。所以你無法靠改用非確定性來繞過 a^n b^n 這道牆；那是同一道牆。
那麼什麼能突破？恰好再多一小片「對的」記憶體。給機器一個堆疊——一疊盤子，你只能往最上面放或從最上面拿——你就得到一台下推自動機。現在 a^n b^n 變得容易了：每讀一個 a 就推入一個盤子，再為每個 b 彈出一個盤子，只有在輸入結束的同時堆疊恰好清空才接受。這個堆疊是無界的，所以它能裝下任何計數；限制你只能碰最上面，正是讓它仍弱於一台完整電腦記憶體的原因。這一次升級，就是從正規語言通往階層下一圈的橋樑，也正是這座階梯下一階梯的起點。DFA 的這道牆不是故事的結局——它是通往文法與下推自動機的那道門。