子集构造法

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

如果我們在狀態 {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 狀態，總共有 2n 這種集合，它們都是 DFA 可能有的節點。如果我們如例子中這樣只建立必須的節點，我們經常會建立一個非常小的 DFA 的。不管如何，仍有必須所有 2n 個狀態的情況，這是不可避免的。

## 形式定義

設 **M** = (_S_, Σ, _T_, _s_, _A_) 是非確定有限狀態自動機。

定義 5 - 元組 **Md** = (_Sd_, _Σd_, _Td_, _sd_, _Ad_)，這裡的

* _Sd_ = _P(S)_
* _Σd_ = Σ
* _sd_ = _Cε(s)_
* _Td(q, a)_ = _Cε_(∪∀ r ∈ q T(r, a))   ∀q ∈ _Sd_, ∀ a ∈ Σ
* _Ad_ = {_q_ | _q_ ∈ _Sd_ ∧ _q_ ∩ _A_ ≠ ∅}

P (S) 是 S 的冪集；

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

可以數學上證明 **Md** 是接受同 **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.）_