Question

DFA 理解和实现起来都很简单，但那是因为它与我们熟悉的机器非常相似。在去除一台真实计算机的所有复杂性之后，我们有机会使用不太常见的思想进行实验了，这将让我们远离熟悉的机器，并可以不必处理把这些思想落实到真实系统中时可能遇到的各种困难。

一种探索方式是去掉我们现有的假设和约束。首先，确定性约束似乎是个限制：可能我们并不关心每个状态上每个可能的输入，那么为什么不能忽略不关心的字符处理规则，而假设异常发生时这台机器能进入到一个通用的失败状态呢？更异乎寻常的是，如果允许这台机器拥有互相对立的规则，以致有多条可能的执行路径，这将意味着什么呢？我们之前的设置还假设，每一个状态改变一定对应从输入流读入一个字符，但是如果在不进行读取的时候机器也能改变状态，将会怎样呢？

在这一节，我们将探索这些想法，在对有限自动机的能力稍做调整之后，看看是否有什么新的可能性。

3.2.1　非确定性

假设我们想要一台有限自动机，它能接受由a 和b 组成的第三个字符是b 的任意字符串。此时很容易想出一个合适的DFA 设计：

如果想要一台机器能接受倒数第三个字符是b 的字符串，怎么办呢？那将如何工作呢？似乎更加困难：上面的DFA 能保证在读第三个字符的时候处于状态3，但是一台机器无法预先知道什么时候能读到倒数第三个字符，因为在结束读取之前它不知道这个字符串有多长。甚至这样的一台DFA 是否可能存在都不一定能立刻清楚。

但是，如果我们放松确定性的限制，并且允许规则手册对于一个状态和输入包含多条规则（或者根本没有规则），那么就可以设计一台能完成任务的机器：

这是一台非确定性有限自动机（NFA），对每一个输入序列不再只有一条执行路径。处于状态1 并且读入b 的时候，它可能会按照一条规则仍保持在状态1，但也可能会按照另一条规则进入状态2。反过来，一旦进入状态4，它找不到任何规则可以遵守，因此没法再继续读取输入。一台DFA 的下一状态总是完全由它的当前状态和输入决定，但是一台NFA 在向下一个状态转移时会有多种可能性，而且有时候根本无法转移。

如果一台DFA 读取一个字符串然后完全按照规则执行，并且最终终止于一个接受状态，那它就能接受这个字符串。那么对于一台NFA 来说，什么才能表示一台NFA 接受或者拒绝一个字符串呢？很自然的回答是，如果存在某条路径能让NFA 按照它的某些规则执行并终止于一个接受状态，那它就能接受这个字符串; 这就是说，即使不是必然的，只要终止于一个接受状态是可能的就可以。

例如，这台NFA 接受字符串'baa'，因为从状态1 开始，有一条路径可以让这台机器读取一个b 转移到状态2，再读取一个a 转移到状态3，最后读一个a 终止于状态4，这是一个接受态。它还接受字符串'bbbbb'，因为NFA 可以在读取前两个b 的时候，按照另一条规则执行并停留在状态1，然后在读第三个b 的时候使用规则转移到状态2，再读取字符串的其他部分，并向以前那样终止于状态4。

另一方面，没有读取'abb' 并终止于状态4 的方法（取决于遵照的不同规则，它最终只能终止于状态1、2 或者3），因此这台NFA 不接受'abb'。'bbabb' 也不行，它最多只能到达状态3：如果读入第一个b的时候直接转移到状态2，它将很快终止于状态4，这样留下两个字符没有处理但是已经没有规则可用了。

能被一台特定机器接受的字符串集合称为一种语言：我们说这台机器识别了这种语言。不是所有的语言都有一台DFA 或者NFA 能识别它们（详见第4章），但那些能被有限自动机识别的语言称为正则语言（regular language）。

放松确定性约束已经造就了一台虚拟机器，这台虚拟机器与我们现实中熟悉的确定性机器差别很大。一台NFA 按照可能性而不是确定性工作：我们根据可能发生的而不是将要发生的来讨论它的行为。这似乎很强大，但是这样的机器在现实世界中如何工作呢？初看上去，现实中一台NFA 的实现需要某种预见性，要在读取输入的时候从几种可能性中做出选择：为了保留接受一个字符串的可能，示例NFA 一定要在读到倒数第三个字符之前保持在状态1，但它没法知道还将收到多少个字符。我们怎么用乏味又确定的Ruby 模拟这样一台激动人心的机器呢？

在确定性计算机上模拟一台NFA，关键是找到一种方法探索出这台机器所有可能的执行。这种暴力方法把所有的可能全都摆出来，以此避免了只模拟一种可能执行时所需要的“幽灵般”的预见性。一台NFA 读到一个字符的时候，它下一步转移到什么状态只会有有限数目的可能性，因此我们模拟非确定性时可以尝试遍历所有可能，然后看它们中哪个最终到达一个接受状态。

尝试遍历所有可能时可以采用递归的方式：每当所模拟的NFA 读取一个字符并且有多个可用的规则时，遵照其中的一条规则，然后尝试读取输入的后续部分；如果这没有让机器到达一个可接受状态，就回退到早期状态，把输入也倒回早期的位置，然后按照另一个不同的规则再次尝试；如此重复，直到某次选择的规则让机器到达一个接受状态，或者所有可能的选择进行遍历的结果都不成功为止。

还有一个策略是采用并行的方式模拟所有可能：每当机器有超过一条规则可以遵守时就创建新线程，并把需要模拟的NFA 复制过去以便复制的每一份都能尝试一条新规则，然后观察它的结果。所有这些线程都能同时执行，每个都从它自己的输入字符串副本中读取。

如果任何一个线程让机器读取了整个字符串，并且停止于一个接受状态，那么可以说这个字符串已经被接受了。这两个实现都是可行的，但是有些复杂和低效。我们模拟的DFA 非常简单，而且能读取单个字符并报告这台机器是否处于一个接受状态，因此要是能模拟一台有同样简单和透明的NFA 就好了。

幸运的是，存在一个简单的方式模拟NFA，而无需回退进程、创建线程或者预先知道所有的输入字符。事实上，就像通过跟踪一台DFA 的当前状态来模拟它一样，我们可以通过跟踪一台NFA 当前所有可能的状态模拟一台简单的NFA。这样比模拟要转移到不同方向的多份NFA 更简单更高效，且最终能完成同样的事情。之前，如果我们模拟很多份独立的机器，那么只需要注意它们每一个都处于什么状态，但处于同样状态的机器是完全无法分辨的2，因此我们把所有可能都压缩到一台机器上并询问“到现在为止它可能处于什么状态”，这样就不会失去任何东西了。

2一台有限自动机不记录自己的历史，除了它的当前状态也不做任何存储，因此处于同样状态的两台相同的机器不管出于什么目的都是可以互换的。

举个例子，让我们演练一下在读取字符串'bab' 时示例NFA 会发生什么。

· 在 NFA读取任何输入之前，它肯定处于起始状态，也就是状态1。

· 读取第一个字符 b。在状态 1，有一个 b 的规则可以让 NFA 停留在状态 1，并且还有一个b 的规则可以把它转移到状态2，这样我们知道之后它可能处于状态1 或者状态2。这些都不是接受状态，这表明NFA 不可能通过读字符串'b' 到达一个接受状态。

· 读取第二个字符 a。如果它处于状态 1，那么只有一个a 的规则可以用，这让它继续处于状态1；如果它处于状态2，就只能按照a 的规则转移到状态3。它一定会终止于状态1 或者状态3，而这些又都不是接受状态，因此没有方法让字符串'ba' 被这台机器接受。

· 读取第三个字符 b。如果它处于状态 1，那么就像以前一样，继续处于状态 1 或者转移到状态2；如果它处于状态3，那就一定会转移到状态4。

· 现在我们知道 NFA 在读取整个输入字符串之后可能处于状态 1、状态 2 或者状态 4。状态4 是一个接受状态，并且我们的模拟表明一定有某种方式让机器通过读取那个字符串到达状态4，因此这个NFA 确实能接受'bab'。

这个模拟策略很容易转换成代码。首先，我们需要一个适合存储NFA 规则的规则手册。当我们询问DFA 规则手册处于特定状态的DFA 读到一个特定的字符之后下一步应该转移到何处时，它总会返回一个状态。但是，NFA 规则手册需要回答一个不同的问题：在NFA 处于几种可能状态之一时，它读取到一个特定的字符，可能的下一个状态是什么呢？实现如下：

require 'set'

class NFARulebook < Struct.new(:rules)
  def next_states(states, character)
    states.flat_map { |state| follow_rules_for(state, character) }.to_set
  end

  def follow_rules_for(state, character)
    rules_for(state, character).map(&:follow)
  end

  def rules_for(state, character)
    rules.select { |rule| rule.applies_to?(state, character) }
  end
end

为了存储由#next_states 返回的可能状态，我们使用Ruby 标准库中的Set类。我们本来可以使用Array 类，但是Set 类有三个有用的特性。

1.它自动去除重复元素。Set[1,2,2,3,3,3] 与Set[1,2,3] 等价。 2.它不关心元素的顺序。Set[3,2,1] 与Set[1,2,3] 等价。 3.它提供标准的集合操作，比如交集（#&）、并集（#+）以及子集测试（#subset?）。

第一个特性很有用，因为“这台NFA 处于状态3 或者状态3”这句话是讲不通的，而且返回一个Set 能确保永远不会包含任何重复数据。其他两个特性的益处将在稍后显现。

我们可以创建一个非确定性的规则手册并向它提问：

>> rulebook = NFARulebook.new([
    FARule.new(1, 'a', 1), FARule.new(1, 'b', 1), FARule.new(1, 'b', 2),
    FARule.new(2, 'a', 3), FARule.new(2, 'b', 3),
    FARule.new(3, 'a', 4), FARule.new(3, 'b', 4)
  ])
=> #<struct NFARulebook rules=[...]>
>> rulebook.next_states(Set[1], 'b')
=> #<Set: {1, 2}>
>> rulebook.next_states(Set[1, 2], 'a')
=> #<Set: {1, 3}>
>> rulebook.next_states(Set[1, 3], 'b')
=> #<Set: {1, 2, 4}>

下一步就是实现一个NFA 类来表示这台模拟的机器：

class NFA < Struct.new(:current_states, :accept_states, :rulebook)
  def accepting?
    (current_states & accept_states).any?
  end
end

方法NFA#accepting? 通过检查是否在current_states 和accept_states 的交集里存在任何状态来完成自己的工作——也就是说，检查当前的可能状态是否也是一个接受状态。

这个NFA 类与我们之前的DFA 类非常相似。不同的是，它有一个当前可能的状态集合current_states 而不是只有一个当前的确定状态current_state，因此如果current_states里有一个是接受状态，就说它处于接受状态：

>> NFA.new(Set[1], [4], rulebook).accepting?
=> false
>> NFA.new(Set[1, 2, 4], [4], rulebook).accepting?
=> true

就像DFA 类一样，我们可以实现一个#read_character 方法读取输入中的一个字符，以及一个#read_string 方法可以按顺序读取几个字符：

class NFA
   def read_character(character)
    self.current_states = rulebook.next_states(current_states, character)
   end

   def read_string(string)
    string.chars.each do |character|
     read_character(character)
    end
   end
end

这些方法实际上与它们对应的DFA 几乎完全相同，只是在#read_character 中使用了current_states 和next_states，而不是current_state 和next_state。

困难的工作结束了。现在我们可以启动一个模拟的NFA，给它传入字符，并且询问它目前的输入是否已经被接受：

>> nfa = NFA.new(Set[1], [4], rulebook); nfa.accepting?
=> false
>> nfa.read_character('b'); nfa.accepting?
=> false
>> nfa.read_character('a'); nfa.accepting?
=> false
>> nfa.read_character('b'); nfa.accepting?
=> true
>> nfa = NFA.new(Set[1], [4], rulebook)
=> #<struct NFA current_states=#<Set: {1}>, accept_states=[4], rulebook=...>
>> nfa.accepting?
=> false
>> nfa.read_string('bbbbb'); nfa.accepting?
=> true

就像我们在使用DFA 类时看到的那样，可以很方便地使用一个NFADesign 对象根据需要自动生产新的NFA 实例，而不是手工创建它们：

class NFADesign < Struct.new(:start_state, :accept_states, :rulebook)
  def accepts?(string)
    to_nfa.tap { |nfa| nfa.read_string(string) }.accepting?
  end

  def to_nfa
    NFA.new(Set[start_state], accept_states, rulebook)
  end
end

这让同一台NFA 检查不同的字符串更容易：

>> nfa_design = NFADesign.new(1, [4], rulebook)
=> #<struct NFADesign start_state=1, accept_states=[4], rulebook=...>
>> nfa_design.accepts?('bab')
=> true
>> nfa_design.accepts?('bbbbb')
=> true
>> nfa_design.accepts?('bbabb')
=> false

就是这样了。我们已经通过模拟一台非同寻常的非确定性机器的所有可能执行，并构建了它的一个简单实现。非确定性是一个设计更复杂有限自动机的非常方便的工具，因此我们很幸运能把NFA 投入实际使用而不只是把它作为理论中的珍品。

3.2.2　自由移动（free move）

我们已经看到，对确定性约束的放松带来了设计机器的新方式，我们不再需要殚精竭力地去实现它们了。为了得到更多的设计自由，我们还可以安全地放松哪些约束呢？

很容易设计一台DFA，能接受长度是2 的倍数的、由字符a 组成的字符串（'aa'、'aaaa'……）：

但是如何设计一台机器，让它能接受长度是2 或3 的倍数的字符串呢？我们知道非确定性让一台机器可以走多于一条的执行路径，因此或许可以设计一台NFA，它有一条“2 的倍数”的路径和一条“3 的倍数”的路径。一个初步的尝试可能看起来像这个样子：

这台NFA 的思想是，在状态1 和状态2 之间移动以接受像'aa' 和'aaaa'这样的字符串，在状态1、状态3 和状态4 之间移动以接受像'aaa' 和'aaaaaaaaa' 这样的字符串。这工作得很好，但问题是这台机器还会接受字符串'aaaaa'，因为它可以从状态1 转移到状态2然后读完前两个字符的时候回到状态1，再在状态3 和状态4 之间转移，之后在读完接下来的三个字符之后回到状态1，终止于一个接受状态，即使这个字符串的长度不是2 或者3 的倍数。3

3实际上，这台NFA 接受字符a 组成的任何字符串，但只有一个字符的字符串'a' 除外。

这次，一台NFA 是否能完成这个工作还不是很明显，但是我们可以引入一个叫作自由移动的机器特性来解决此问题。这些规则让机器无需读取任何输入就能自发遵照执行，并且它们在这儿提供帮助是因为能让NFA 在两组状态之间做一个初步选择：

自由移动表示成从状态1 到状态2 和状态4 的无标记虚线箭头。机器仍然接受字符串'aaaa'，它会先自发地转移到状态2，然后随着读取输入在状态2 和状态3 之间转移。类似地，如果它开始先自由移动到状态 4 也能接受'aaaaaaaaa'。但是现在它没法接受字符串'aaaaa'了：不管做任何可能的执行，它都一定要从到状态2 或者状态4 的转移开始，而且一旦选择了其中一条路径转移之后，就没法退回来了。一旦处于状态2，就只能接受一个长度是2 的倍数的字符串，同样一旦处于状态4，就只能接受长度是3 的倍数的字符串。

如何用Ruby 模拟NFA 中的自由移动呢？当然，是保持在状态1、自发地转移到状态 2，还是自发地转移到状态 4，这些新选择并不比已有的非确定性奇怪多少，并且我们的实现能够用类似的方式处理它。我们已经有了一台模拟机一次可以有多个可能状态的思想，因此只需要拓展那些可能的状态，把通过执行一次或者多次自由移动能到达的状态包括进来。在这种情况下，“机器从状态 1 开始”的真正意思是：在没有读取任何输入之前，它可能处于状态1、2 或4。

首先，我们需要一种用Ruby 表示自由移动的方法。最简单的方法就是使用正常的FARule实例，只是在一个字符的位置上填上一个nil。NFARulebook 的现有实现将像处理其他任何字符一样处理nil，因此我们可以询问：“从状态1，通过执行一次自由移动（而不是问：“……通过读入一个字符a ？”），能到达什么状态？”

>> rulebook = NFARulebook.new([
    FARule.new(1, nil, 2), FARule.new(1, nil, 4),
    FARule.new(2, 'a', 3),
    FARule.new(3, 'a', 2),
    FARule.new(4, 'a', 5),
    FARule.new(5, 'a', 6),
    FARule.new(6, 'a', 4)
  ])
=> #<struct NFARulebook rules=[...]>
>> rulebook.next_states(Set[1], nil)
=> #<Set: {2, 4}>

下一步需要一些辅助代码帮助找到从一个特定集合的状态开始，通过自由移动所能到达的所有状态。这些代码只能反复自由移动，因为只要存在从当前状态出发的自由移动，一台NFA 就可以多次自发改变状态。可以把它很方便地放到NFARulebook 类的一个方法里：

class NFARulebook
  def follow_free_moves(states)
    more_states = next_states(states, nil)

    if more_states.subset?(states)
      states
    else
      follow_free_moves(states + more_states)
    end
  end
end

NFARulebook#follow_free_moves 以递归的方式查找越来越多的状态，这些状态能从一个给定的集合通过自由移动到达。再也找不到时，即由next_states(states,nil) 找到的每一个状态都已经包含在states 里时，它就返回找到的所有状态。4

4确切地说，这个过程计算了“通过自由移动增加更多状态”函数的定点。

以下代码正确地识别出NFA 在读取任何输入之前的可能状态：

>> rulebook.follow_free_moves(Set[1])
=> #<Set: {1, 2, 4}>

现在通过覆盖NFA#current_states 已有的实现（就像覆盖Struct 提供的方法一样），我们把对自由移动的支持加入到NFA 当中。新的实现将与NFARulebook#follow_free_moves 挂钩，并确保自动机当前可能的状态总是包含通过自由移动能到达的任何状态：

class NFA
  def current_states
    rulebook.follow_free_moves(super)
  end
end

因为其他所有NFA 方法都是通过调用#current_states 访问当前可能状态的集合，所以这种透明性让我们不必改动NFA 代码的其他部分就能支持自由移动。

这就全部完成了。现在模拟支持自由移动了，而且现在能看看哪些字符串能被我们的NFA接受了：

>> nfa_design = NFADesign.new(1, [2, 4], rulebook)
=> #<struct NFADesign ...>
>> nfa_design.accepts?('aa')
=> true
>> nfa_design.accepts?('aaa')
=> true
>> nfa_design.accepts?('aaaaa')
=> false
>> nfa_design.accepts?('aaaaaa')
=> true

自由移动实现起来非常简单，并且在非确定性的基础之上给了我们额外的设计自由。

本章中有一些非传统术语。有限自动机读取的字符通常叫作符号（symbol），状态之间移动的规则叫作转移（transition），组成一台机器的规则集合叫作转移函数（有时候也叫NFA 的转移关系）而不是规则手册。因为表示空字符串的数学符号是希腊字母ε，能自由移动的NFA 称为NFA-ε，自由移动本身通常称为ε 转移。