幂集构造

在计算理论中，幂集构造是转换非确定有限状态自动机（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中建立标记“${\displaystyle \emptyset }$ ”的新状态，从这里没有出路；所有它的外出边都指向自身，并且它不是接受状态。我们接着在DFA中增加从{4}到${\displaystyle \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.）