幂集构造

维基百科,自由的百科全书
跳转至: 导航搜索

计算理论中,幂集构造是转换非确定有限状态自动机(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:

NFA-powerset-construction-example.svg

我们将构造一个等价的 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-powerset-construction-example.svg
最终结果 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 中建立标记“\emptyset”的新状态,从这里没有出路;所有它的外出边都指向自身,并且它不是接受状态。我们接着在 DFA 中增加从 {4} 到 \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 状态,总共有 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.)