冪集構造

計算理論中,冪集構造是轉換非確定有限狀態自動機(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」的一個邊。

最終結果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中建立標記「 」的新狀態,從這裡沒有出路;所有它的外出邊都指向自身,並且它不是接受狀態。我們接着在DFA中增加從{4}到 標記「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 | qSdqA ≠ ∅}

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.)