[科普中国]-幂集构造

在计算理论中，幂集构造是转换非确定有限状态自动机（NFA）到识别同样语言的确定有限状态自动机（DFA）的标准方法。

简介幂集构造在理论上的重要性源于它确立了NFA尽管有额外的灵活性，它不能识别不能被任何DFA识别的任何语言。在实践中的重要性源于它把易于构造的NFA转换成了更有效执行的DFA。但是如果NFA有n个状态，结果的DFA可能有最多2个状态，这种指数增长有时使这种构造对于大NFA而言是不实际的。1

动机回想一下，NFA除了特定节点可能有“分支”引出同时前进的多个路径之外，它和DFA是一样的。NFA将接受输入字符串，如果在计算完成的时候它的路径之一结束于一个接受状态。如果它的所有路径都失败，它就拒绝输入字符串。例如，在例子图中，如果我们在状态2而下一个输入符号是1，机器分支，行进到状态2和4二者。

注意不管NFA从一个状态中引出有多少不同的路径，它们每个在看到一个字符之后都必定到达n个状态中的一个。因此，给定以前的选择序列，我们可以简洁的总结NFA当前格局（configuration）为它在那个时刻可能处于的状态的集合。此外，我们如果我们知道NFA当前处在的状态的集合，我们可以指出基于下一个输入符号我们可以访问哪个状态集合。这就是算法的关键。1

定义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个状态的情况，这是不可避免的。2

形式定义设M= (S, Σ,T,s,A)是非确定有限状态自动机。

定义5-元组Md= (Sd,Σd,Td,sd,Ad)，这里的

Sd=P(S)

Σd= Σ

sd=Cε(s)

Td(q, a)=Cε(∪∀ r ∈ qT(r, a)) ∀q ∈Sd, ∀ a ∈ Σ

Ad= {q|q∈Sd∧q∩A≠ ∅}

P(S)是S的幂集；

Cε(q)是q的ε-闭包，就是说从q经过一次或多次ε-转移可到达的所有状态的集合。

可以数学上证明Md是接受同M一样语言的确定有限状态自动机。2

计算理论计算理论（英语：Theory of computation）是数学的一个领域，和计算机有密切关系。其中的理论是现代密码协议、计算机设计和许多应用领域的基础。该领域主要关心三个方面的问题：

采用什么计算模型（即形式语言、自动机）

解决哪些是能计算的、哪些是不能计算的（即可计算性理论及算法）

要用多少时间、要用多少存储（即计算复杂性理论）

这三方面的问题可以用一个问题来总括：“电脑的基础能力及限制到什么程度？”

计算理论的“计算”并非指纯粹的算术运算（Calculation），而是指从已知的输入透过算法来获取一个问题的答案（Computation），因此，计算理论属于计算机科学和数学。

为了对计算进行严谨的研究，计算机科学家会将计算以数学的方式抽象化，称为计算模型。有几种目前在使用的计算模型，其中最出名的是图灵机。计算机科学家研究图灵机的原因是它很容易叙述，可以分析，用来证明结果，而且用此模式呈现了许多强而有力的计算模型（引用邱奇－图灵论题）。图灵机有潜在的，数量无限的记忆能力，这似乎是不可能达到的，不过所有图灵机解决的可判定性问题都只需要有限量的记忆能力。因此理论上，任何可以用图灵机解决的（可判定性）问题都只需要有限量的记忆能力。2

本词条内容贡献者为:

方正 - 副教授 - 江南大学