冪集構造

在計算理論中，冪集構造是轉換非確定有限狀態自動機（NFA）到識別同樣語言的確定有限狀態自動機（DFA）的標準方法。它在理論上的重要性源於它確立了NFA儘管有額外的靈活性，它不能識別不能被任何DFA識別的任何語言。在實踐中的重要性源於它把易於構造的NFA轉換成了更有效執行的DFA。但是如果NFA有n個狀態，結果的DFA可能有最多2ⁿ個狀態，這種指數增長有時使這種構造對於大NFA而言是不實際的。

動機

回想一下，NFA除了特定節點可能有「分支」引出同時前進的多個路徑之外，它和DFA是一樣的。NFA將接受輸入字符串，如果在計算完成的時候它的路徑之一結束於一個接受狀態。如果它的所有路徑都失敗，它就拒絕輸入字符串。例如，在例子圖中，如果我們在狀態2而下一個輸入符號是1，機器分支，行進到狀態2和4二者。

注意不管NFA從一個狀態中引出有多少不同的路徑，它們每個在看到一個字符之後都必定到達n個狀態中的一個。因此，給定以前的選擇序列，我們可以簡潔的總結NFA當前格局（configuration）為它在那個時刻可能處於的狀態的集合。此外，我們如果我們知道NFA當前處在的狀態的集合，我們可以指出基於下一個輸入符號我們可以訪問哪個狀態集合。這就是算法的關鍵。

例子

考慮下列有字母表{0, 1}的NFA:

我們將構造一個等價的DFA；最終結果展示在後面。我們開始於開始狀態。NFA開始於狀態1，但是它可以不查看任何輸入就沿着ε邊前進到狀態2和3。所以我們必須認為它最初同時處於這些狀態。我們為DFA建立一個初始狀態並標記上「{1,2,3}」。

接着，假設我們看到輸入字符0。如果我們處在狀態1，我們可以沿着標記0的邊前進到狀態2。如果我們處在狀態3，我們可以前進到狀態4。如果我們處在狀態2，我們就被粘住了；沒有0邊出於狀態2。這意味着NFA放棄從狀態1沿着ε邊到狀態2的這條舊路徑；它現在處在狀態2和4之中。我們在DFA中增加從開始狀態到標記着「{2,4}」的一個新狀態的標記着「0」的一個新邊。

假設我們最初看到的輸入字符是1。則狀態1的兩個路徑和狀態3的路徑不能前進，但狀態2的路徑可以並且它分支了：它同時保持在狀態2和前進到狀態4。因此，NFA現在在狀態2和4中，就是說完全同於對0輸入字符，但原因不同。我們在DFA中向從開始狀態到現存的「{2,4}」狀態的邊增加標記「1」。

現在，假設我們在{2,4}狀態並看見了字符1。在狀態4中的路徑不能前進，但是在狀態2再次去到了2或4二者。我們仍在狀態{2,4}中。如果我們看到了字符0，我們可以從從狀態4前進到狀態3，但不能從狀態2前進到狀態3。此外，在到達狀態3之後，我們分支並也從ε-邊到達狀態2。結果是處在狀態2和3。我們在DFA增加標記「{2,3}」的一個狀態和從{2,4}到{2,3}的標記「0」的一個邊。

最終結果DFA

如果我們在狀態{2,3}看到了字符1，狀態3的路徑不能前進，但是在狀態2的路徑前進到狀態2和4，同前面一樣這回到了節點{2,4}。如果我們看到字符0，狀態2的路徑不能繼續，而在狀態3的路徑可以到達狀態4。因此，我們只能到達狀態4。我們在DFA中建立標記「{4}」的一個新狀態和從{2,3}到{4}的標記「0」的一個邊。

最後，如果我們在狀態{4}並看到輸入0，我們同前面一樣前進到狀態2和3，所以，在DFA中建立從{4}到{2,3}的一個標記「0」的邊。如果我們看到了輸入1，我們餘下的所有路徑都被粘住了而機器必須拒絕輸入字符串。怎麼辦呢?我們在DFA中建立標記「 $\emptyset$ 」的新狀態，從這裡沒有出路；所有它的外出邊都指向自身，並且它不是接受狀態。我們接着在DFA中增加從{4}到 $\emptyset$ 標記「1」的邊。

現在我們已經考慮了所有可能情況。我們必須決定的是在這個DFA哪個狀態應當接受。因為NFA接受輸入字符串，如果任何它的路徑結束於接受狀態，我們可以通過設置所有包含接受NFA狀態的DFA狀態節點，為接受狀態了模仿，也就是設置{1,2,3}, {2,3}, {2,4}和{4}為接受狀態。結果的DFA完全接受同最初的NFA同樣的字符串集合。注意這個DFA比最初的NFA更大。

定義DFA

我們來概括上述過程。定義一個DFA有四個重要問題必須回答：

什麼是狀態？
那些狀態是接收狀態？
什麼狀態是開始狀態？
一個狀態到下一個狀態如何刻畫？

我需要一個DFA的狀態來描述NFA的每個可能格局。但是一般的說，NFA在任何給定點都可以處在它的狀態的任何子集中。集合S的子集的集合叫做冪集，並寫為P(S)，我們定義在DFA中的狀態集合是在NFA中狀態集合的冪集。這回答了第一個問題。

我們已經提及了如果在NFA中任何並行路徑在結束時處在接受狀態，則NFA接受輸入字符串。DFA可以通過在包含某NFA接受狀態之一的任何狀態中接受輸入來模擬。這回答了第二個問題。

對於第三個問題。假設給NFA的輸入字符串是空串。在它必須停止之前它可以訪問什麼狀態?她不能沿着標記了輸入符號的任何邊前進，但它可以沿不消耗任何輸入的ε邊前進。因為它可以到達從開始狀態之使用ε表到達的任何狀態。這個狀態集合形式上叫做開始狀態的ε-閉包。因為我們的DFA在給予空輸入串的時候時候除了立即停止不能做任何事情，我們必須保證DFA的開始狀態包括所有可能的這些NFA狀態。我們通過設置DFA的開始狀態為NFA開始狀態的ε-閉包來完成。

最後，我們使用類似的想法回答第四個問題。假設我們處在DFA的特定狀態中（就是說，NFA狀態的特定集合中）看到了特定輸入符號，想知道下DFA的一個狀態是什麼。精確的回答是：從當前的NFA狀態集合基於這個輸入符號可以訪問到NFA狀態的集合。要得出這個集合，我們查看每一個NFA當前狀態，並詢問「給定這個輸入符號，從這能到哪裡呢?」。答案就是可沿着標記着這個輸入符號的任何單一邊，和任何數目的ε邊前進。我們以這種方式查找並發現我們可以觸及的所有節點，並把它們加入下一個狀態的節點集合中。當我們對所有當前NFA狀態完成了這個工作，我們就有了對應於特定DFA狀態的NFA狀態的集合，並增加從當前DFA狀態到這個狀態的標記着這個輸入符號的一個邊。

一旦我們已經對所有DFA狀態和所有符號完成了這個過程，我們的DFA就完成了。結果的機器跟蹤了NFA在輸入字符串的每個時刻訪問的狀態的集合。但是，這個機器是非常大的：因為每個NFA的狀態集合可能包含任何特定NFA狀態，總共有2ⁿ這種集合，它們都是DFA可能有的節點。如果我們如例子中這樣只建立必須的節點，我們經常會建立一個非常小的DFA的。不管如何，仍有必須所有2ⁿ個狀態的情況，這是不可避免的。

形式定義

設M = (S, Σ, T, s, A)是非確定有限狀態自動機。

定義5-元組M_d = (S_d, Σ_d, T_d, s_d, A_d)，這裡的

S_d = P(S)
Σ_d = Σ
s_d = C_ε(s)
T_d(q, a) = C_ε(∪_{∀ r ∈ q} T(r, a)) ∀q ∈ S_d, ∀ a ∈ Σ
A_d = {q | q ∈ S_d ∧ q ∩ A ≠ ∅}

P(S)是S的冪集；

C_ε(q)是 q的ε-閉包，就是說從q經過一次或多次ε-轉移可到達的所有狀態的集合。

可以數學上證明M_d是接受同M一樣語言的確定有限狀態自動機。

引用

Michael Sipser, Introduction to the Theory of Computation ISBN 0-534-94728-X. （See . Theorem 1.19, section 1.2, pg. 55.）
John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X. （See chapter 2.）