
_START_ARTICLE_
幂集构造
_START_PARAGRAPH_
在计算理论中，幂集构造是转换非确定有限状态自动机（NFA）到识别同样语言的确定有限状态自动机（DFA）的标准方法。它在理论上的重要性源于它确立了NFA尽管有额外的灵活性，它不能识别不能被任何DFA识别的任何语言。在实践中的重要性源于它把易于构造的NFA转换成了更有效执行的DFA。但是如果NFA有n个状态，结果的DFA可能有最多2ⁿ个状态，这种指数增长有时使这种构造对于大NFA而言是不实际的。
_START_SECTION_
动机
_START_PARAGRAPH_
回想一下，NFA除了特定节点可能有“分支”引出同时前进的多个路径之外，它和DFA是一样的。NFA将接受输入字符串，如果在计算完成的时候它的路径之一结束于一个接受状态。如果它的所有路径都失败，它就拒绝输入字符串。例如，在例子图中，如果我们在状态2而下一个输入符号是1，机器分支，行进到状态2和4二者。_NEWLINE_注意不管NFA从一个状态中引出有多少不同的路径，它们每个在看到一个字符之后都必定到达n个状态中的一个。因此，给定以前的选择序列，我们可以简洁的总结NFA当前格局（configuration）为它在那个时刻可能处于的状态的集合。此外，我们如果我们知道NFA当前处在的状态的集合，我们可以指出基于下一个输入符号我们可以访问哪个状态集合。这就是算法的关键。
_START_SECTION_
例子
_START_PARAGRAPH_
考虑下列有字母表{0, 1}的NFA:_NEWLINE_我们将构造一个等价的DFA；最终结果展示在后面。我们开始于开始状态。NFA开始于状态1，但是它可以不查看任何输入就沿着ε边前进到状态2和3。所以我们必须认为它最初同时处于这些状态。我们为DFA建立一个初始状态并标记上“{1,2,3}”。_NEWLINE_接着，假设我们看到输入字符0。如果我们处在状态1，我们可以沿着标记0的边前进到状态2。如果我们处在状态3，我们可以前进到状态4。如果我们处在状态2，我们就被粘住了；没有0边出于状态2。这意味着NFA放弃从状态1沿着ε边到状态2的这条旧路径；它现在处在状态2和4之中。我们在DFA中增加从开始状态到标记着“{2,4}”的一个新状态的标记着“0”的一个新边。_NEWLINE_假设我们最初看到的输入字符是1。则状态1的两个路径和状态3的路径不能前进，但状态2的路径可以并且它分支了：它同时保持在状态2和前进到状态4。因此，NFA现在在状态2和4中，就是说完全同于对0输入字符，但原因不同。我们在DFA中向从开始状态到现存的“{2,4}”状态的边增加标记“1”。_NEWLINE_现在，假设我们在{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”的一个边。_NEWLINE_如果我们在状态{2,3}看到了字符1，状态3的路径不能前进，但是在状态2的路径前进到状态2和4，同前面一样这回到了节点{2,4}。如果我们看到字符0，状态2的路径不能继续，而在状态3的路径可以到达状态4。因此，我们只能到达状态4。我们在DFA中建立标记“{4}”的一个新状态和从{2,3}到{4}的标记“0”的一个边。_NEWLINE_最后，如果我们在状态{4}并看到输入0，我们同前面一样前进到状态2和3，所以，在DFA中建立从{4}到{2,3}的一个标记“0”的边。如果我们看到了输入1，我们余下的所有路径都被粘住了而机器必须拒绝输入字符串。怎么办呢?我们在DFA中建立标记“”的新状态，从这里没有出路；所有它的外出边都指向自身，并且它不是接受状态。我们接着在DFA中增加从{4}到标记“1”的边。_NEWLINE_现在我们已经考虑了所有可能情况。我们必须决定的是在这个DFA哪个状态应当接受。因为NFA接受输入字符串，如果任何它的路径结束于接受状态，我们可以通过设置所有包含接受NFA状态的DFA状态节点，为接受状态了模仿，也就是设置{1,2,3}, {2,3}, {2,4}和{4}为接受状态。结果的DFA完全接受同最初的NFA同样的字符串集合。注意这个DFA比最初的NFA更大。