上一階梯留下的缺口
在上一階梯，你建造並運行了確定型有限自動機——一個像旋轉閘門的控制器，除了目前的狀態外什麼都不記得，且每讀一個輸入符號就遵循恰好一條規則 delta(q, a) = p（在狀態 q、讀到符號 a 時，移動到狀態 p）。定義它的關鍵字是確定性：從任一狀態出發，每個符號都指向唯一一個下一狀態，所以機器整趟運行是一條單一、完全被決定的路徑。你也認識了它的根本極限——有限記憶體無法無上限地計數，這正是為什麼 a^n b^n 落在正規語言之外。
確定性極為可預測，但它會讓設計機器變得痛苦。假設你想恰好接受字母表 Sigma = {a, b} 上以 a b b 結尾的字串。一個人從左讀到右時會不斷猶豫：「這個 a 是最後那段 a b b 的開頭，還是只是中間隨便一個 a？」DFA 不能猶豫——它必須當下就決定，不准偷看後面。本階梯要介紹一台被允許猶豫的機器：它會把自己分裂，平行地探索好幾種未來。
猜測與分身：核心想法
一台非確定型有限自動機，也就是 NFA，外觀幾乎和 DFA 一樣，但它的轉移規則在一個大膽的地方放寬了：從某個狀態出發、讀到某個符號時，它可以指向零個、一個或多個下一狀態。於是規則不再是 delta(q, a) = p（單一狀態），而變成轉移到一組狀態：delta(q, a) = {p1, p2, ...}，甚至可能是空集合。請把這幅畫面記在腦中——分身。每當機器面臨好幾個選擇時，就想像它分裂成一個選擇配一個分身，而每個分身都各自獨立地讀完剩下的輸入。
這帶出一個顯而易見的問題：既然有許多分身在跑，由誰決定機器是否接受？這條規則——NFA 的接受條件——是極度樂觀的：只要至少有一個分身停在接受狀態，NFA 就接受這個字串。換句話說，只要存在某一條逐個符號選擇下來的路徑落在接受狀態，就接受。唯有當每個分身都死掉（走進空的下一狀態集合）或停在非接受狀態時，這個字串才會被拒絕。一條成功的路徑就足以致勝。
一個小例子：以 a b b 結尾的字串
看看分身如何化解設計者的頭痛。我們要 {a, b} 上所有以 a b b 結尾的字串。建一台四狀態的 NFA，狀態為 q0、q1、q2、q3，起始狀態 q0，只有 q3 是接受狀態。從 q0 讀到 a 時放兩條轉移：一條 a 自迴圈回到 q0（這個分身說「我還在略過中間的雜訊」），另一條 a 到 q1（這個分身猜「最後的 a b b 就從這裡開始」）。其餘只是驗證這個猜測：q1 讀 b 到 q2，q2 讀 b 到 q3。讀到任何其他符號時，猜測中的那個分身根本沒有可走的轉移，於是死掉。
NFA for "ends in a b b" (start = q0, accept = q3)
state | on a | on b
------+---------------+-----------
q0 | {q0, q1} | {q0}
q1 | { } | {q2}
q2 | { } | {q3}
q3 | { } | { }
Run on input a b a b b (track the SET of live clones):
start : {q0}
read a : {q0, q1} (q0 stayed, and guessed -> q1)
read b : {q0, q2} (q1 -> q2 ; q0 looped ; guess q1 had no... wait)
read a : {q0, q1} (q2 had no 'a' move and died; q0 stayed+guessed)
read b : {q0, q2} (q1 -> q2 ; q0 loops)
read b : {q0, q3} (q2 -> q3 ; q0 loops)
q3 is in the final set ==> ACCEPT (some clone reached q3)關於那段追蹤，有兩點要誠實說明。第一，當狀態 q2 讀到 a 時，它的目標是空集合，所以那個特定的分身就直接消失了——沒有錯誤、沒有當機，它只是不再是一條活路徑；這就是 NFA 默默放棄錯誤猜測的方式。第二，你其實不會真的跑無限多個分身；模擬 NFA 的實際做法，是在每一步追蹤「此刻可能有活分身佔據」的那一組狀態。這種把所有路徑平行探索看成一組狀態的觀點，正是我們在最後遇到的那個轉換法的種子。
為什麼非確定性不是作弊
這感覺像作弊：機器彷彿魔法般「知道」最後那段 a b b 從哪裡開始。但這裡沒有神諭，也沒有運氣。理解 NFA 的乾淨方式是猜測再驗證：想像機器在每個岔路（這裡是最後的模式從哪裡開始）都猜一個選擇，接著確定性地一路讀下去驗證這個猜測。接受規則只是說：若存在某個能被驗證成功的猜測，這個字串就屬於該語言。沒有任何東西是靠機率算出來的；我們是用「存在」這個詞，對所有可能的猜測作量化。
NFA 還有一項靈活之處，我們在這裡只先點名，留到下一篇展開：一條完全不消耗任何輸入符號的轉移，寫在空字串 epsilon（希臘字母 ε）上。這樣的ε-轉移讓一個分身能「免費」漂移到另一個狀態，於是把較小的機器黏接起來變得毫不費力。現在你只要知道它存在即可；用來馴服它的ε-閉包，正是緊接著的下一個主題。
能力相同，機器更小——以及一個警告
這裡有一個讓整座階梯既美麗又有點出人意料的結論：非確定性並不會多給你任何識別能力。NFA、ε-NFA 與 DFA 三者識別的，恰好是同一類語言——正規語言。這就是NFA 與 DFA 等價定理。所以 NFA 同樣永遠識別不了 a^n b^n；非確定性只買到精簡與設計上的便利，買不到觸及範圍。容易的那個方向是：每台 DFA 本來就已經是一台 NFA；令人驚奇的方向則是：每台 NFA 都能被攤平回某台 DFA。
把 NFA 攤平成 DFA 的訣竅，就是子集構造法（也叫冪集構造法），而你在上面那段追蹤裡已經看見了它的心跳。既然模擬 NFA 就等於追蹤「可能有活分身佔據的那一組狀態」，那就乾脆把每一個這樣的集合當成一台全新 DFA 的單一狀態。完整流程我們會用一整個階梯來跑，但這四步的骨架短到現在就可以先嚐一口。
- DFA 的起始狀態，就是只含 NFA 起始狀態的那個集合（之後會被 ε-轉移擴張）。
- 對目前的集合 S 與符號 a，下一個 DFA 狀態就是把每個 q 屬於 S 的 delta(q, a) 取聯集——正是「任一活分身讀到 a 能去哪裡」。
- 持續產生新的可達集合，直到不再冒出新集合為止；這一定會結束，因為子集只有有限多個。
- 一個 DFA 狀態（一個集合）是接受狀態，恰好當它含有至少一個 NFA 的接受狀態時——正好對應「只要有分身在接受狀態就接受」。
這裡有一個你該帶往後面的誠實陷阱。一台有 n 個狀態的 NFA 有 2^n 個可能的子集，所以做出來的 DFA 在最壞情況下可能多達 2^n 個狀態——也就是令人聞之色變的指數爆炸。這不只是理論上的擔憂：確實有些真實語言，其最小的 NFA 約有 n 個狀態，而每一台 DFA 都需要大約 2^n 個。所以這兩種模型在能力上相等，在大小上卻可能天差地遠；而這個取捨——用小而好設計的 NFA 來設計，再（有時昂貴地）付出代價去確定化——正是本階梯留給你的實用教訓。