同等威力，更小的機器

四篇導覽，一個出人意料的結論

這一階梯用四個步驟給了你一台更豐富的機器。首先你認識了非確定性這種分身術：在岔路上機器分裂成多份，各自試走不同的分支，而只要「任何一個」分身抵達接受狀態，輸入就被接受。接著你讓一次轉移落到一整「組」下一狀態，而不只是一個，並加入了epsilon 移動——不讀任何符號就改變狀態，再用 epsilon 閉包把所有免費可達的狀態一網打盡。然後你看見了這為何讓設計變得輕鬆。最後，子集構造把任何這樣的機器變回一台普通的 DFA。本篇把這四者綁在一起，把那句關鍵結論清楚說出來。

結論一口氣說完：凡是 NFA 能識別的語言，都有某台 DFA 也能識別；而凡是 epsilon-NFA 能識別的語言，都有某台普通 NFA（因此也有某台 DFA）能識別。這三種機器等價——可以完全互換。其中一台接受的，另外兩台也接受；其中一台拒絕的，另外兩台也拒絕。它們不是三種威力——它們是同一種威力穿著三套戲服。

為什麼等價成立，而且雙向都成立

等價是一條雙向道，而其中一個方向幾乎是白送的。一台 DFA 本來就是一台 NFA——一台格外自律的 NFA，它的每次轉移恰好落到只含一個狀態的集合，沒有岔路、沒有 epsilon 移動。所以 DFA 所做的一切都不超出 NFA 的能耐；真正需要做的工是另一個方向：證明每一台 NFA 都能壓平成一台 DFA。那個較難的方向，正是上一篇的子集構造，而那個讓它行得通的訣竅，值得再回味一次。

追蹤一個「集合」，而不是單一狀態。你建造的 DFA，其每一個狀態對應 NFA 狀態的一個子集。一個 DFA 狀態的意思是「此刻那些分身可能身處的那一組精確的 NFA 狀態」。
從 NFA 起始狀態的 epsilon 閉包出發——也就是在讀任何東西之前就可達的每一個狀態。那一組就是 DFA 的起始狀態。
讀到符號 a 時這樣前進：從目前這組出發，取每個 NFA 狀態在 a 上的轉移，把所有目標聯集起來，再對結果取 epsilon 閉包。那唯一一組集合就是下一個 DFA 狀態。
若某個 DFA 狀態的集合裡至少含有 NFA 的一個接受狀態，就把這個 DFA 狀態標記為接受——這正是「有某個分身成功了」這條規則。

為什麼這會讓結果變成確定型？因為一「組」NFA 狀態在每個符號之下都恰有唯一一個後繼集合——集合聯集與 epsilon 閉包都是函數，它們只回傳一個答案。把整團分身當成一個整體來看，即便每個分身都在猜，這團雲卻是確定地行軍。接受規則完美地映照了 NFA 接受：一個集合算作接受，當且僅當其中至少有一個分身已經成功。這就是困難方向的全部證明，再配上那個白送的方向，就得到了 NFA 與 DFA 的等價。把「epsilon 閉包這一步本來就吸收了 epsilon 移動」這件事一併納入，你還會得到 DFA 等於 NFA 等於 epsilon-NFA——三種模型等價，全都恰好識別正規語言。

更小——但有一個最壞情況的代價

既然這些機器等價，那何必還要用 NFA？因為它們通常小得多、也好設計得多——這就是 NFA 的簡潔性。當你想要「輸入以 abb 結尾」時，NFA 可以乾脆猜測「abb 就從這裡開始」然後驗證，只需寥寥幾個狀態；而等價的 DFA 必須在每一個位置都記住「目前為止這個模式已匹配了多少」。NFA 讓你說出「你要『什麼』」，把記帳的活兒交給非確定性；DFA 卻逼你親手把帳全記了。

但子集構造也暗示了一個代價。一台 n 個狀態的 NFA 有 2^n 個可能的子集，所以它產生的 DFA 原則上可能需要多達 2^n 個狀態。通常大多數子集都不可達，真正的 DFA 很小；但對某些精心構造的語言，這個爆炸是真的會咬人的：存在一些 n 個狀態的 NFA，其最小的等價 DFA 確實需要約 2^n 個狀態。這就是指數爆炸，而它不是演算法的弱點——它是這兩種表示法之間一個真實、可證明的大小落差。

Classic blowup family:  L_n = { strings whose n-th symbol from the END is 'a' }, over {a,b}

NFA  (n+1 states):  guess WHEN the n-th-from-end position arrives, then check n-1 more symbols.

  ->(q0) --a,b--> (q0)            stay, still scanning
     (q0) ---a---> (q1)           GUESS: 'this a is the n-th from the end'
     (q1) --a,b--> (q2) ... (qn)  verify exactly n-1 more symbols follow
     (qn) = accept

DFA:  must remember the LAST n symbols seen (cannot guess) ->  needs 2^n states.

  small, lazy NFA   (n+1 states)
  vs
  big, bookkeeping DFA   (2^n states)   <- the blowup is provably unavoidable here

「倒數第 n 個符號」語言：NFA 只要 n+1 個狀態，但每一台等價的 DFA 都需要約 2^n 個狀態。

持久的教訓：非確定性是一個裝置

現在來到整個階梯最深的收穫，這一條要帶著爬完餘下的階梯。非確定性是一種數學上的便利——不是一種更強大的機器，也不是一塊硬體。它不是隨機：一台非確定機器不會擲硬幣然後碰運氣。它的接受規則是這句謹慎的話——「只要『有某條』路通向接受就接受」——這是在斷言「在所有可能的路徑之中，存在一條好路」，彷彿由一位完美的神諭來評估：只要存在正確的猜測，它就總是猜對。沒有任何實體機器能「免費試遍所有路徑」；要真的運行一台 NFA，你得模擬它，而誠實的做法就是子集構造，它可能要付出那 2^n 個狀態的代價。

那麼，既然非確定性不增添威力、又不是真實硬體，為什麼還要留著它？因為它是一個絕佳的設計與證明工具。它把一個問題俐落地切成兩半：對你尚未知道的部分先「猜測」（abb 從哪裡開始、要試哪個因數），再確定地「驗證」這個猜測。設計那個猜測者很簡單；接著子集構造會替你做掉「把它變確定型」這件煩瑣的事。這個「先猜後驗」的模式，並不是有限自動機的奇趣小玩意——它正是這座階梯遠處等著你的最大想法之一的心跳：NP 這個類別，在那裡一個問題難以求解，但只要有人遞給你一張猜出來的證書，就容易驗證。你在這裡造出的那台分身機器，正是你與那個想法最初、也最溫柔的一次相遇。

你現在能做什麼，又指向何方

退一步，數數這一階梯為你換來了什麼。你現在能用那種偷懶又富表達力的方式設計機器——猜測與分身，把 epsilon 移動和子集構造留給後續收拾——而且你「有證明地」知道：那台便利的機器與那台嚴格的確定型機器，接受的語言完全相同。你也知道在壓平一台 NFA 時要預期可能的指數爆炸，並且知道「不要」把非確定性誤認作威力、隨機或硬體。

關鍵在於，DFA 那一階梯立下的邊界並沒有移動。NFA、epsilon-NFA 與 DFA 全都恰好識別正規語言——而且請記得「正規」不等於「有限」（無限語言 Sigma-star 與 a* 都是正規語言）。由有限記憶體極限砌起的那道牆依然矗立：a^n b^n 仍然不被這三者中的任何一台識別，因為它們都無法無界地計數。接下來的階梯以兩種方式回應這道牆：正規「表示式」給你一套恰好描述這些語言的代數，而幫浦式的論證讓你證明某個語言落在它們之外。你在這裡掌握的分身術會持續帶來紅利，一路向上直到 NP。