Question

本章已经描述了确定性状态机的思想，并且为它增加了更多特性。首先是非确定性，在设计机器时它能提供很多可能的执行路径。还有自由移动，它让非确定性的机器无需读取任何输入就可以改变状态。

非确定性和自由移动让设计有限状态机执行特定的工作更容易——我们已经看到它们在把正则表达式转换成状态机时非常有用——但它们为我们做了什么标准DFA 不能做的事情吗？

把任何非确定性有限自动机转成接受完全相同字符串的确定性自动机是可能的。考虑到一台DFA 的额外约束，这可能有些令人吃惊。但在思考一下我们对两种机器执行的模拟方式之后，这就能讲得通了。

假如我们要模拟一台特定DFA 的行为。对这个假想DFA 读取一个特定字符序列的模拟可能会是这样：

· 机器读取任何输入之前，它处于状态 1；

· 机器读取字符'a'，那么它现在处于状态 2；

· 机器读取字符'b'，那么它现在处于状态 3；

· 不再有输入，而且状态 3 是一个接受状态，所以字符串'ab' 已经被接受。

这里有一些很微妙的东西：模拟在重新创造着DFA 的行为。在我们的例子里，模拟是运行在一台真实计算机上的Ruby 程序，而DFA 则是无法运行的一台抽象机器，因为它根本不存在。每当假想的DFA 改变状态的时候，正在运行的模拟也要改变——因此才称其为模拟。

很难把DFA 和它的模拟分开，因为它们都是确定性的，而且它们的状态完全匹配：DFA处于状态2 的时候，模拟也处于一个能表明“这台DFA 处于状态2”的状态。在我们的Ruby 模拟中，这个模拟状态实际上就是DFA 实例的current_state 属性值。

尽管在处理非确定性和自动移动时有额外的开销，但对一个假想的NFA 读取字符串进行模拟并没有什么大的不同。

· 机器读取任何输入之前，它可能处于状态 1 或者状态 3。7

· 机器读取字符 c，那么现在它可能处于状态 1、3 或者 4 中的一个。

· 机器读取字符 d，那么现在它可能处于状态 2 或者状态 5 中的一个。

· 不再有输入，并且状态 5 是一个接受状态，因此字符串 'cd' 已经被接受。

7尽管一台NFA 只有一个起始状态，但自由移动使得读取任何输入之前进入其他状态成为可能。

模拟的状态与NFA 的状态不一样，这一点此时更容易看出来。事实上，在模拟的每一点上，我们一直都无法确定NFA 那时处于什么状态。但是模拟本身仍然是确定性的，因为它的状态能够适应这种不确定性。在NFA 可能处于状态1、3 或者4 中一个的时候，我们可以肯定模拟现在处于一个表示“NFA 处于状态1、3 或者4”的某一个确定状态。

这两个例子的唯一真正区别是，DFA 的模拟是从一个当前状态移动到另一个，而NFA 的模拟是从一个当前可能状态的集合移动到另一个可能状态的集合。尽管一个NFA 的规则手册可以是非确定性的，但是对于一个给定的输入从当前状态出发移动到哪些状态，这个决定总是完全确定性的。

这种确定性意味着我们总可以构造一台DFA 来模拟一台特定的NFA。这台DFA 有一个状态表示这台NFA 的每一个可能状态的集合，并且DFA 状态之间移动的规则对应着NFA的确定性模拟在它可能状态的集合之间的移动方式。这台DFA 将能够完全模拟NFA 的行为，并且只要为DFA 选择合适的接受状态——根据我们的Ruby 实现，这些将是与处于接受状态的NFA 对应的任何状态——它也将接受同样的字符串。

让我们尝试着为一台特定的NFA 做这种转换。以下面这个为例：

在没有读取任何输入之前，这台NFA 可能处于状态1 或者状态2（状态1 是起始状态，而状态2 可以通过自由移动到达），因此模拟将从可以叫作“1 或者2”的状态开始。从这个起点出发，根据它读到的是a 或b，模拟将会在不同的状态终止。

· 如果读到 a，模拟仍将保持在状态“1 或者 2”：NFA 处于状态 1 时它可以读入a，然后或是维持在状态1 或是进入状态2，而从状态2 开始，它没法再读入a 了。

· 如果读到 b，NFA可能会终止于状态 2 或者状态 3（从状态 1 开始），它不能再读到 b 了，但是从状态2 开始，它可以移动到状态3 并且还可能自由移动回状态2；因此，我们说输入为b 的时候，模拟将移动到叫作“2 或者3”的状态。

通过思考一个NFA 模拟的行为，我们可以为这个模拟构造一台状态机：

“2 或者3”是模拟的一个接受状态，因为状态3 是NFA 的一个接受状态。

可以继续这个过程发现模拟的更多新状态，直到不再有新发现为止。因为原始NFA 的状态只有有限数目的可能组合，所以最后肯定能停止发现。8 通过重复对示例NFA 的发现过程，我们发现从“1 或者2”出发然后读取a 和b 的序列，它的模拟只能碰到四种不同的状态组合：

8模拟一个三状态的NFA 时，最差情况是“1”“2”“3”“1 或者2”“1 或者3”“2 或者3”“1、2 或者3”和“无”。

如果NFA处于状态……	并且读入字符……	它可能终止于状态……
1 或2	a	1 或2
	b	2 或3
	2 或3	a	无
		b	1、2 或3
		无	a	无
			b	无
			1、2或3	a	1 或2
				b	1、2 或3

此表完整地描述了一台DFA，如下图所示，它与原始的NFA 接受同样的字符串：

这个DFA 只比我们开始的NFA 多出一个状态，而且对于一些NFA，这个过程可能会产生比原始机器的状态更少的DFA。但是在最坏情况下，一台有n个状态的NFA 可能需要一台有2ⁿ 个状态的DFA，因为n 个状态总共有2ⁿ 个可能组合（考虑把每个组合都表示成一个n 比特的数字，其中第n 个比特表示状态n 是否包含在这个组合中），并且模拟可能需要访问其中所有的组合而不仅仅是其中一部分。

下面我们用Ruby 实现这个NFA 到DFA 的转换。策略是引入一个新的类NFASimulation，用来收集NFA 模拟的信息然后把这些信息汇总成一台DFA 。NFASimulation 根据特定的NFADesign 创建，并且最后提供一个#to_dfa_design 方法把它转换成等价的DFADesign。

我们已经有了可以模拟NFA 的NFA 类，因此NFASimulation 可以创建NFA 的实例，然后操纵这个实例弄清楚对所有可能的输入它们都是如何响应的。在开始写NFASimulation 之前，我们先回到NFADesign 并且给NFADesign#to_nfa 增加一个可选的参数“当前状态”，这样就可以使用任意集合的当前状态构建一台NFA，而不是只能使用NFADesgin 的起始状态：

class NFADesign
  def to_nfa(current_states = Set[start_state])
    NFA.new(current_states, accept_states, rulebook)
  end
end

此前，一台NFA 的模拟只能从它的起始状态开始，但这个新的参数让它可以从其他任何点起步：

>> rulebook = NFARulebook.new([
    FARule.new(1, 'a', 1), FARule.new(1, 'a', 2), FARule.new(1, nil, 2),
    FARule.new(2, 'b', 3),
    FARule.new(3, 'b', 1), FARule.new(3, nil, 2)
  ])
=> #<struct NFARulebook rules=[...]>
>> nfa_design = NFADesign.new(1, [3], rulebook)
=> #<struct NFADesign start_state=1, accept_states=[3], rulebook=...>
>> nfa_design.to_nfa.current_states
=> #<Set: {1, 2}>
>> nfa_design.to_nfa(Set[2]).current_states
=> #<Set: {2}>
>> nfa_design.to_nfa(Set[3]).current_states
=> #<Set: {3, 2}>

这个NFA 类自动把自由移动考虑进来了——可以看到NFA 从状态3 开始的时候，无需读取任何输入它就可能处于状态2 或者3。因此为了支持自由移动，我们不用做任何特别的事情。

现在我们可以用任何可能状态的集合创建一台NFA，向其输入一个字符，然后看它最终可能处于什么状态。这是把一台NFA 转换成一台DFA 重要的一步。在NFA 处于状态2 或者3 并且读入一个b 的时候，之后它可能处于什么状态呢？

>> nfa = nfa_design.to_nfa(Set[2, 3])
=> #<struct NFA current_states=#<Set: {2, 3}>, accept_states=[3], rulebook=...>
>> nfa.read_character('b'); nfa.current_states
=> #<Set: {3, 1, 2}>

答案是状态1、2 或者3，就像我们在手工转换过程中发现的那样。（请记住，集合中元素的顺序没关系。）

让我们使用这个思想创建NFASimulation 类，给它增加一个方法计算模拟的状态如何根据某一个特定的输入而改变。我们把模拟的状态看成这台NFA 当前可能状态的集合（例如“1、2 或者3”），因此可以写一个#next_state 方法，以一个模拟的状态和一个字符为参数，把这个字符传递给对应那个状态的一台NFA，之后通过监视这台NFA 得到一个新的状态：

class NFASimulation < Struct.new(:nfa_design)
  def next_state(state, character)
    nfa_design.to_nfa(state).tap { |nfa|
      nfa.read_character(character)
    }.current_states
  end
end

这里讨论的两种状态很容易让人感到迷惑。模拟的一个状态（NFASimulation#next_state 的state 参数）是许多NFA 状态的一个集合，这是为什么我们可以把它作为NFADesign#to_nfa 的current_states 参数的原因。

这让我们可以很方便地考察模拟的不同状态：

>> simulation = NFASimulation.new(nfa_design)
=> #<struct NFASimulation nfa_design=...>
>> simulation.next_state(Set[1, 2], 'a')
=> #<Set: {1, 2}>
>> simulation.next_state(Set[1, 2], 'b')
=> #<Set: {3, 2}>
>> simulation.next_state(Set[3, 2], 'b')
=> #<Set: {1, 3, 2}>
>> simulation.next_state(Set[1, 3, 2], 'b')
=> #<Set: {1, 3, 2}>
>> simulation.next_state(Set[1, 3, 2], 'a')
=> #<Set: {1, 2}>

现在需要一种方式能系统地考察模拟的状态并把我们的发现记录成一台DFA 的状态和规则。我们打算直接使用每个模拟的状态作为一个DFA 状态，因此第一步是实现NFASimulation#rules_for，它使用#next_state 发现每一个规则的目的状态，从一个特定的模拟状态出发构建出全部规则。“全部规则”意味着它是对每一个可能的输入字符适用的一个规则，因此我们还定义了辅助方法NFARulebook#alphabet 来了解原始的NFA 可以读取哪些字符：

class NFARulebook
  def alphabet
    rules.map(&:character).compact.uniq
  end
end

class NFASimulation
  def rules_for(state)
    nfa_design.rulebook.alphabet.map { |character|
      FARule.new(state, character, next_state(state, character))
    }
  end
end

如预期一样，这让我们看到了在不同的状态之间不同的输入将会如何模拟：

>> rulebook.alphabet
=> ["a", "b"]
>> simulation.rules_for(Set[1, 2])
=> [
  #<FARule #<Set: {1, 2}> --a--> #<Set: {1, 2}>>,
  #<FARule #<Set: {1, 2}> --b--> #<Set: {3, 2}>>
]
>> simulation.rules_for(Set[3, 2])
=> [
  #<FARule #<Set: {3, 2}> --a--> #<Set: {}>>,
  #<FARule #<Set: {3, 2}> --b--> #<Set: {1, 3, 2}>>
]

方法#rules_for 让我们可以通过已知的模拟状态发现新的状态，并且通过反复对其执行，我们可以找到所有可能的模拟状态。我们可以使用NFASimulation#discover_states_and_rules 方法，它采用类似NFARulebook#follow_free_moves 的方法递归找到更多的状态。

class NFASimulation
  def discover_states_and_rules(states)
    rules = states.flat_map { |state| rules_for(state) }
    more_states = rules.map(&:follow).to_set

    if more_states.subset?(states)
      [states, rules]
    else
      discover_states_and_rules(states + more_states)
    end
  end
end

#discover_states_and_rules并不关心模拟状态背后的状态，而只有这个状态才能用作#rule_for 的参数。但是作为程序员，还有一个地方可能让我们困惑。变量states 和more_states 是模拟状态的集合，但是我们知道每一个模拟状态本身是一个NFA 状态的集合，因此states 和more_states 实际上是NFA 状态集合的集合。

最初，我们只知道模拟的一个状态：NFA 进入起始状态时的可能状态集合。#discover_states_and_rules 从这个起点开始探索，最终找到所有的4 个状态和模拟的8 个规则：

>> start_state = nfa_design.to_nfa.current_states
=> #<Set: {1, 2}>
>> simulation.discover_states_and_rules(Set[start_state])
=> [
    #<Set: {
    #<Set: {1, 2}>,
    #<Set: {3, 2}>,
    #<Set: {}>,
    #<Set: {1, 3, 2}>
    }>,
  [
#<FARule #<Set: {1, 2}> --a--> #<Set: {1, 2}>>,
#<FARule #<Set: {1, 2}> --b--> #<Set: {3, 2}>>,
#<FARule #<Set: {3, 2}> --a--> #<Set: {}>>,
#<FARule #<Set: {3, 2}> --b--> #<Set: {1, 3, 2}>>,
#<FARule #<Set: {}> --a--> #<Set: {}>>,
#<FARule #<Set: {}> --b--> #<Set: {}>>,
#<FARule #<Set: {1, 3, 2}> --a--> #<Set: {1, 2}>>,
#<FARule #<Set: {1, 3, 2}> --b--> #<Set: {1, 3, 2}>>
]
]

最后我们要知道的是，每一个模拟状态是否应该被处理成一个接受状态，但是在模拟中很容易通过查询NFA 得到结果：

>> nfa_design.to_nfa(Set[1, 2]).accepting?
=> false
>> nfa_design.to_nfa(Set[2, 3]).accepting?
=> true

既然我们有了模拟DFA 的所有部件，现在只需一个NFASimulation#to_dfa_design 方法把它们封装成一个DFADesign 实例：

class NFASimulation
  def to_dfa_design
    start_state = nfa_design.to_nfa.current_states
    states, rules = discover_states_and_rules(Set[start_state])
    accept_states = states.select { |state| nfa_design.to_nfa(state).accepting? }

    DFADesign.new(start_state, accept_states, DFARulebook.new(rules))
  end
end

就这样。我们可以使用任何NFA 构造一个NFASimulation 实例，并把它转换成一个接受同样字符串的DFA：

>> dfa_design = simulation.to_dfa_design
=> #<struct DFADesign ...>
>> dfa_design.accepts?('aaa')
=> false
>> dfa_design.accepts?('aab')
=> true
>> dfa_design.accepts?('bbbabb')
=> true

棒极了！

在本节的开始，我们问过NFA 的额外特性是否能做一台DFA 完成不了的事情。现在很明显答案为否，因为如果任何NFA 都可以转成一台做同样工作的DFA，那么NFA 就不会有额外的能力。非确定性和自由移动只是一台DFA 已经能做的工作的再包装，就像编程语言里中的语法糖一样，它们不是让我们超越确定性约束的新能力。

理论上说，为一台简单的机器增加更多的特性却没有为它根本上增加更多的能力非常有趣，但实际上这是很有用的，因为一台DFA 比一台NFA 更容易模拟：只有一个当前状态要跟踪，并且一台DFA 用硬件或者机器代码实现起来足够简单，可以使用程序存储位置作为状态，用条件分支作为规则。这意味着一个正则表达式的实现可以把一个模式先转换成一台NFA 然后再转换成一台DFA，得到一台能被快速高效模拟的非常简单的机器。

DFA 最小化

一些DFA 的特性是最小化的，就是说无法设计出一台能接受同样字符串但是状态更少的DFA。NFA 到DFA 的转换过程有时候会产生包含冗余状态的非最小化DFA，但是有一种优雅的方式可以去除这种冗余，叫作Brzozowski 算法。

1.从你的非最小化DFA 开始。

2.反转所有规则。从形象的表示上说，这意味着表示机器的图上每一个箭头都保持原位但是方向反转；从代码上说，每一个FARule.new(state, character, next_state) 被替换成FARule.new(next_state,character, state)。反转规则通常会打破确定性约束，因此现在你有了一台NFA。

3.交换起始状态和接受状态的角色：起始状态成为接受状态，而每一个接受状态成为一个起始状态。（因为一台NFA 只有一个起始状态，所以你不能直接把所有的接受状态变成起始状态，但是你可以创建一个新的起始状态，然后通过自由移动把它与 每一个旧的接受状态连接起来，这样效果是一样的。）

4.把这个反转的NFA 按通常方式转换成一台DFA。

奇怪的是，这样得到的DFA 保证是最小的而且不含冗余状态。遗憾的缺点是它只能接受原始DFA 字符串的颠倒版本：如果我们原始的DFA 接受字符串'ab'、'aab'、'aaab' 等，那这个最小化的DFA 将接受'ba'、'baa' 和'baaa' 形式的字符串。修正方法是简单地第二次执行整个过程，从反转的DFA 开始再得到一个二次反转的DFA，它还能保证是最小的，但这次能接受与我们开始的那台机器一样的字符串了。

能有一种自动的方法去除设计中的冗余是很美好的。但有趣的是，一台最小化的DFA也是标准的：接受完全相同字符串的任何两台DFA 将最小化成为同样的机器，因此我们可以把两台NFA 最小化然后比较结果看它们结构是否相同，以此来检查两台DFA是否等价。9 这反过来提供了一种优雅的方法，可以检查两个正则表达式是否等价：如果我们把与同一个字符串匹配的两个模式（例如ab(ab)* 和a(ba)*b）转换成NFA，把这些NFA 转成DFA，然后把两台DFA 使用Brzozowski 算法最小化，最终将得到两台看起来一样的机器。

9解决这个图的同构问题本身要求一个聪明的算法，但非正式地检查两台机器的结构图并确定它们是否“相同”却足够简单。