冪集構造

在計算理論中，冪集構造是轉換非確定有限狀態自動機（NFA）到識別同樣語言的確定有限狀態自動機（DFA）的標準方法。

基本介紹

• 中文名：冪集構造
• 特點：靈活性
• 性質：計算理論
• 領域：計算機

簡介

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

動機

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

注意不管NFA從一個狀態中引出有多少不同的路徑，它們每個在看到一個字元之後都必定到達n個狀態中的一個。因此，給定以前的選擇序列，我們可以簡潔的總結NFA當前格局（configuration）為它在那個時刻可能處於的狀態的集合。此外，我們如果我們知道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一樣語言的確定有限狀態自動機。

計算理論

計算理論（英語：Theory of computation）是數學的一個領域，和計算機有密切關係。其中的理論是現代密碼協定、計算機設計和許多套用領域的基礎。該領域主要關心三個方面的問題：

• 採用什麼計算模型（即形式語言、自動機）
  
• 解決哪些是能計算的、哪些是不能計算的（即可計算性理論及算法）
  
• 要用多少時間、要用多少存儲（即計算複雜性理論）
  

這三方面的問題可以用一個問題來總括：“電腦的基礎能力及限制到什麼程度？”

計算理論的“計算”並非指純粹的算術運算（Calculation），而是指從已知的輸入透過算法來獲取一個問題的答案（Computation），因此，計算理論屬於計算機科學和數學。

為了對計算進行嚴謹的研究，計算機科學家會將計算以數學的方式抽象化，稱為計算模型。有幾種目前在使用的計算模型，其中最出名的是圖靈機。計算機科學家研究圖靈機的原因是它很容易敘述，可以分析，用來證明結果，而且用此模式呈現了許多強而有力的計算模型（引用邱奇－圖靈論題）。圖靈機有潛在的，數量無限的記憶能力，這似乎是不可能達到的，不過所有圖靈機解決的可判定性問題都只需要有限量的記憶能力。因此理論上，任何可以用圖靈機解決的（可判定性）問題都只需要有限量的記憶能力。