為什麼需要這個：把「猜測」變成一部跑得動的機器
到現在，你已能生動地想像一部非確定型有限自動機：讀到每個符號時，它不挑一個動作，而是把自己複製出來、同時嘗試所有被允許的動作，而只要某一個分身停在接受狀態，它就接受這個字串。第 3 篇說明了為什麼這讓 NFA 設計起來如此愜意。但真實電腦無法真的分叉出一支複製大軍——它一次只執行一個確定的步驟。於是一個合理的問題懸在空中：如果非確定性只是個思考輔具，我們究竟該如何真的執行一部 NFA，而它會不會偷偷比一部普通的 DFA 更強大？
這兩個問題的答案是同一個漂亮的想法。你不需要追蹤哪一個分身在哪裡——你只需要追蹤「讀完目前為止的輸入後，NFA 可能處於的狀態集合」。那個集合是關於過往的、單一而定義明確的事實，正是 DFA 能裝進一個狀態裡的那種有界摘要。子集構造法（也叫冪集構造法）會造出一部普通的 DFA，它的每一個狀態都是這樣一個集合。執行那部 DFA，你實際上就等於並行地跑完了所有分身，卻從不曾真的分叉。
食譜，一步一步來
以下是完整的構造。我們從一部 NFA 出發，它有狀態集合 Q、字母表 Sigma（輸入符號的集合）、轉移關係 delta、起始狀態 q0、與接受集合 F。我們要造一部 DFA，它的狀態名稱是 Q 的子集。如果這部 NFA 有 ε-轉移，那麼我們碰到的每一個集合，都必須先對 ε-閉包封閉——也就是第 2 篇那個運算，它在讀任何符號之前，先免費把所有沿著 ε（epsilon，空字串）箭頭可達的狀態都加進來。
- DFA 的起始狀態：取 {q0} 的 ε-閉包。那單一個集合就是 DFA 的起點——它捕捉了「在讀任何東西之前，NFA 可能身處的所有位置」。
- DFA 的轉移：對目前的集合 S 與輸入符號 x，把「從 S 中任一狀態讀 x 所能到達的每個 NFA 狀態」全部蒐集起來（也就是對所有 q ∈ S 取 delta(q, x) 的聯集），再取那個結果的 ε-閉包。封閉後的集合就是下一個 DFA 狀態。這樣的集合恰好只有一個，所以這步移動是確定的。
- 惰性地發掘狀態：一開始只放起始集合，每當某個轉移產出一個你沒見過的集合，就把它加進待辦清單。一直做到不再冒出新集合為止。你只會探索「真正可達」的那些子集——通常遠少於全部子集。
- DFA 的接受狀態：一個集合 S 是接受狀態，正當它含有至少一個 NFA 的接受狀態時（S 與 F 相交）。這就是「某個分身接受了」這條規則，換成集合的講法——只要 S 的任一成員落在 F 裡，NFA 就可能停在那裡，於是字串被接受。
看它跑一遍：一部小小的兩狀態 NFA
沒有什麼比親自跑一遍更能把它變具體了。取「以 1 結尾的二進位字串」這個語言，Sigma = {0, 1}。一部自然的 NFA 有兩個狀態。起始狀態 A 在 0 與 1 上都迴圈（它樂呵呵地讀任何前綴），而讀到 1 時它還會猜「這也許是最後一個符號」並移到 B。狀態 B 是接受狀態，沒有任何外出的動作。那個猜測正是重點：A 保留了「停留或跳走」的選項，而所謂接受，就是「至少有一條猜測路徑，恰好在輸入用完時落在 B」。
這部 NFA 沒有 ε-轉移，所以閉包什麼都不做，我們可以直接讀集合。起始集合是 {A}。從 {A} 讀 0，只到得了 A，得 {A}。從 {A} 讀 1，到得了 A（自迴圈）且到得了 B（猜測），得 {A, B}。從 {A, B} 讀 0，A 給出 A、B 什麼都不給，所以是 {A}。從 {A, B} 讀 1，A 給出 {A, B}、B 什麼都不給，所以是 {A, B}。沒有新集合冒出來——我們收工了，四個可能子集中只用到三個可達子集。含有 B 的 DFA 狀態就是接受狀態，也就是 {A, B}。
NFA (ends in 1), Sigma = {0,1}:
start A, accept B
delta(A,0) = {A} delta(A,1) = {A, B}
delta(B,0) = {} delta(B,1) = {}
Subset construction -> DFA. DFA states are sets of NFA states.
DFA state | on 0 | on 1 | accepting?
----------- +-------- +--------- +-----------
-> {A} | {A} | {A, B} | no (no B)
{A, B} | {A} | {A, B} | YES (has B)
-> marks the DFA start state {A}
Trace 1101: {A} -1-> {A,B} -1-> {A,B} -0-> {A} -1-> {A,B} -> accept (ends in 1)
Trace 110 : {A} -1-> {A,B} -1-> {A,B} -0-> {A} -> reject (ends in 0)看看剛剛發生了什麼。NFA 的那個猜測——「現在就跳到 B，賭這是結尾」——被溶解成 DFA 單純地把兩種可能性同時記在集合 {A, B} 裡。DFA 從不賭博；它帶著「所有還活著的選項」的完整集合，到最後再把它讀出來。這是最清楚不過的示範，說明非確定性是一種記帳上的方便，而非什麼魔法引擎：每一個猜測，都化成了一個被記住的集合。
走向確定的代價：指數級爆炸
我們的例子很仁慈——四個可能子集中用了三個。但 DFA 狀態是 NFA 狀態的子集，而一部 n 狀態的 NFA 有 2^n 個子集。在最壞情況下，這個構造真的會碰到「可達集合的數目以 2^n 般增長」，所以一部比方說 20 狀態的 NFA，原則上能逼出一部超過一百萬個狀態的 DFA。這就是著名的指數級爆炸，它不是食譜的瑕疵——它是「拒絕猜測」的誠實代價。
一個經典的見證：「倒數第 n 個符號是 1」的二進位字串語言。一部小 NFA 用約 n + 1 個狀態就能搞定——它只要猜哪個 1 是倒數第 n 個，事後再驗證計數。但任何辨識此語言的 DFA 都至少需要 2^n 個狀態，因為在字串結束之前，它必須精確地記住最後 n 個符號（它無法事先知道哪一個會是倒數第 n 個），而 n 個位元有 2^n 種不同的視窗需要區分。這裡的爆炸不是構造偷懶；它是被語言本身逼出來的。
這個構造證明了什麼：同等威力，不多不少
退一步會發現，子集構造法不只是個工具——它是一個證明。它是一套演算法，接受任何 NFA、產出一部接受完全相同語言的 DFA。再配上那個顯然的事實——每部 DFA 本來就是一部（極其溫馴的）NFA——便給出了那條頭條結論：DFA、NFA、與 ε-NFA 全都辨識完全相同的語言類別，也就是正規語言。這就是三模型的等價性，也是這整個級別的脊梁。
好好品味這份驚訝，因為它正是那個恆久的教訓。非確定性——把自己複製出來探索每一條路徑、只要任一路徑成功就接受——在純粹的威力上半點也買不到。它買到的只有簡潔：更小、更清晰、更易設計的機器（這正是第 3 篇如此倚重它的原因）。它不讓 NFA 辨識任何一個 DFA 辨識不了的語言。所以這裡的「非確定」從來不表示「更有能力」，更絕不表示「隨機」。
此刻正該把任何殘留的誤解送走。NFA 不擲硬幣，它也不是一塊免費的快速硬體——你沒辦法去店裡買一台、它就魔法般地替你分叉。非確定性是一個數學裝置：一個帶著精心挑選之接受規則（「若某條路徑通向接受，便接受」）的定義。子集構造法就是那張收據，證明這個裝置在威力上分文不費，而且永遠能兌換成一部真實、確定的機器。把這個區別保持鋒利——當同一個詞「非確定」之後在圖靈機、以及在類別 NP 的定義裡重新登場時，它會以遠不那麼天真的姿態回來，那裡「非確定性是否免費」正是那道天大的未解難題。