DFA 設計者的負擔
設計一台 DFA 會逼你接受一種奇特的紀律。因為轉移函數是全函數且單值，每個狀態都必須「事先」回答：對每個符號該怎麼辦——而且每個狀態都必須編碼「你目前所學到的事實的『精確組合』」。你不被允許說「我還不確定，先等等看」；機器在每個符號之後都必須鎖定一個狀態，而那個狀態必須足以把工作做完，不論接下來來什麼。對「含偶數個 a」這種簡單語言，這很愉快；可是對「由好幾條彼此重疊的線索」拼成的語言，它就變成沉重的記帳工作。
舉一個具體的反派：在字母表 Σ = {0, 1}（大寫 sigma，即字母表）上，「倒數第三個符號是 1」的二進位字串所成的語言。身為人類，你只會說「等到結尾，再往回看三格」。但 DFA 嚴格由左到右地讀，且不准回頭偷看，所以在每個位置它都必須記住「最近看到的三個符號」——000、001、……、111 共八種可能——因為其中任何一種都可能恰好是最後三個。光是要握住一個三符號的視窗，就要八個狀態，而每多記一個位置，狀態數就再翻一倍。
非確定性讓你「描述」，而不是「記帳」
把同一個語言寫成一台非確定型有限自動機（NFA），它小得幾乎有點欺負人。坐在起始狀態 q0，自由地讀符號，對 0 和 1 都自迴圈——這個狀態的意思是「我還沒猜到那個『倒數第三個符號』已經出現」。從 q0，當你讀到一個 1 時，你「還」有一個選項可以前進到 q1，彷彿在說「我賭『這個』1 就是那一個」。從 q1 讀任意符號到 q2，從 q2 讀任意符號到 q3，並讓 q3 成為唯一的接受狀態。四個狀態，而你是去「猜對起點」，而不是去「記住每一個視窗」。
NFA "third symbol from the end is 1" Sigma = {0,1} start: q0 accept: { q3 }
0,1 (loop)
+----+
| v
-> ( q0 )------ on 1 ----> ( q1 )-- 0,1 --> ( q2 )-- 0,1 --> (( q3 ))
The ONLY nondeterminism: in q0, reading a 1, you may stay in q0 OR jump to q1.
delta(q0, 0) = { q0 } delta(q1, 0) = { q2 }
delta(q0, 1) = { q0, q1 } delta(q1, 1) = { q2 } (and likewise q2 -> q3)
Input 10100, accept if SOME path ends in q3:
the lucky path: q0 -1-> q0 -0-> q0 -1-> q1 -0-> q2 -0-> q3 ends in q3 => ACCEPT
(the 3rd-from-last symbol of 10100 is indeed the underlined 1)這就是把非確定性當成設計工具的全部魅力。回想第 1 篇：NFA 接受一個字串，恰好當「『某一條』選擇路徑通向接受狀態」時——想像你在每個分岔處複製自己，只要有「任何一個」分身愉快地走到終點，你就接受。於是你可以放手寫一台這樣的機器：「在對的時刻，猜『重要的部分就從『這裡』開始』，然後只要『檢查』剩下的部分對得上即可。」這種先猜後驗的形狀——猜出見證，再確定型地驗證它——正是 NFA 較易設計的原因：你只描述「一個好字串長什麼樣子」，而「存在某條路徑」這條規則就默默替你搜遍了每一種可能。
簡潔從何而來——又能大到什麼地步
兩種結構上的自由，賦予了 NFA 的小巧，而把它們點名出來，能幫你看出在哪裡採用它會划算。第一，轉移可以指向一『集合』的狀態：delta(q0, 1) = {q0, q1} 是一條合法的單一規則，它向外散開；而 DFA 卻必須把這種分岔塌縮成一個精挑細選的單一狀態。第二，NFA 不必是全函數——若目前符號沒有對應的箭頭，那條路徑就乾脆「死掉」，無須陷阱狀態，也沒有「把失敗一一寫清楚」的義務。再加上第 2 篇的 ε-轉移（免費的跳躍，由 ε-閉包 黏合起來），你就能像積木一樣把小機器拼接起來——而這正是下一階把正規表示式建造成機器的做法。
所以 NFA 的簡潔 是真實的，有時還很戲劇化。「倒數第 k 個符號是 1」這一族語言，作為 NFA 只需 k+1 個狀態，但可被證明作為 DFA 需要 2^k 個狀態——正是我們上面看到的那種翻倍，如今被陳述成一條定律。這個落差就是著名的指數級爆炸：一台 DFA 可能需要多達 2^n 個狀態，才能做一台 n 狀態 NFA 所做的事。把這稱作「在紙上偏好 NFA 的最深理由」是誠實的：描述可以指數級地更短。
帳單到期：子集構造法
NFA 設計起來很美妙，但照字面看，怎麼「執行」它並不顯然——真實的 CPU 無法分裂成許多分身。化解之道（第 4 篇會完整展開）就是子集構造法（也叫冪集構造法）。它只有一個想法：把「NFA 目前可能身處的『狀態集合』」記下來，藉此「一次模擬所有分身」。一個 NFA 狀態的集合，化身成單一個 DFA 狀態，而從那裡開始，每一步又都是確定型的了。我們先前害怕的那個爆炸就在這裡付清，因為 n 個 NFA 狀態有 2^n 個可能的子集——但實務上多數子集從不出現，所以 DFA 通常遠比那個最壞情況小。
- 起始狀態。DFA 的起始狀態，是「僅靠 ε-轉移就能從 NFA 起始狀態抵達」的那些 NFA 狀態所成的集合——也就是它的 ε-閉包。（若沒有 ε-轉移，這就只是 {q0}。）把它想成「在讀任何東西之前，所有分身可能身在何處？」。
- 對一個符號走一步。從集合 S 出發，讀一個符號 a，就把「從 S 中『任何一個』狀態讀 a 所能抵達」的每一個 NFA 狀態都收集起來，再對結果取 ε-閉包。整個這個集合就是下一個單一的 DFA 狀態——這一步確定型的移動，已默默地讓每一個分身都前進了一格。
- 接受狀態。一個 DFA 狀態（一個集合）是接受的，恰好當它「『包含』至少一個 NFA 接受狀態」時——這正是「『某個』分身愉快」（即某條路徑接受）的忠實翻譯。
- 重複直到封閉。持續產生「新移動所抵達」的集合，直到不再出現新的集合為止。只有「真的出現過」的子集才成為 DFA 狀態，這就是為什麼你通常得到的遠少於 2^n 個。
在「以 1 結尾」風格上嚐一小口。假設一台 NFA 有 delta(A, 0) = {A}、delta(A, 1) = {A, B}，其中 A 是起始狀態、B 是唯一的接受狀態。起始狀態為 {A}。讀 0 時，{A} 走到 {A}；讀 1 時，{A} 走到 {A, B}。如今從 {A, B} 出發，讀 0 抵達 {A}（B 沒有 0 的箭頭，所以那個分身死掉），讀 1 又抵達 {A, B}。這就只有三個子集——{A}、{A, B}，以及「若有任何路徑曾全數死光」時出現的空集——而 {A, B} 是接受的，因為它含有 B。這台兩狀態的 NFA 就變成了一台乾淨、小巧的 DFA，不需要任何分身。
誠實的課題：能力相同，且是個數學裝置
子集構造法證明了一件值得大聲說出來的事：每一台 NFA 都能轉成一台「接受完全相同語言」的 DFA。把它反過來跑，DFA 本來就是一台（非常整潔的）NFA。所以 DFA、NFA、以及第 2 篇的 ε-NFA 全都恰好辨認同一族語言——也就是正規語言。這個 NFA 與 DFA 的等價 是整階的頭條：在這裡，非確定性在「原始能力」上替你買到的是「零」。它不讓有限自動機無上界地計數，也不比 DFA 更能辨認 a^n b^n。它買到的全部，就只是簡潔——在「你必須寫下多少狀態」這件事上，省下可能高達指數級的份量。
這就引出本篇最想退役的迷思：非確定性是一個數學裝置，既不是隨機，也不是免費的硬體。NFA 不擲硬幣——「某條路徑接受」這條規則是一個精確的邏輯量詞（「『存在』一串選擇……」），不是運氣，所以同一個字串永遠給出同一個是或非的裁決。而且沒有任何真實機器能免費分裂：當你最終要執行一台 NFA 時，你要嘛用子集構造法的記帳、要嘛一次探索一條路徑，來「付清」那些分身。猜測是給「設計者」與數學家的方便；它在執行時從來不是折扣。
請牢牢記住這個形狀，因為它會在這座階梯的最頂端，以遠為戲劇化的調性回歸。確定型類別 P 與非確定型類別 NP 之間的關係，正是同一套「先猜後驗」的想法——猜一個憑證，再用多項式時間驗證它。但在那裡，「非確定型版本是否真的更強大」這個問題，也就是 P 對 NP 問題，眾所周知仍是『未解』的。對有限自動機，我們很幸運：子集構造法把它解決了，而答案乾淨俐落地是『同等強大』。這道對比——『此處已證、彼處未決』——正是貫穿整門學科的一條安靜主線。