Question

现实中，计算机通常都有大量的易失存储器（RAM）和非多核易失存储器（硬盘或者SSD），有许多输入/ 输出设备，还有能同时执行多个指令的处理器。有限状态机（finite state machine），也叫有限自动机（finite automaton），是一台计算机的极简模型，为了容易理解、推导并且容易用硬件或软件实现，它放弃了上面所有的这些特性。

3.1.1　状态、规则和输入

有限自动机没有持久化的存储并且几乎没有RAM。它只是一台小机器，拥有一些可能的状态，并能够跟踪到自己当前具体处于其中的哪个状态——试着把它看成一台RAM 只够存储一个值的计算机。同样，有限自动机没有键盘、鼠标和接收输入的网络接口，只有一 个外部的字符输入流可以一次读取一个字符。

每台有限自动机没有通用的CPU 执行任意程序，而是硬编码了一些规则集合，以决定在相应的输入下如何从一个状态切换到另一个状态。自动机先从一个特定的状态开始，然后从输入流中读入字符——按照规则它每次读取一个字符。

下面是一台有限自动机的结构图：

两个圆代表自动机的两个状态——1 和2。凭空出现的箭头表明这台自动机从状态1 开始，1 是它的起始状态。两个状态之间的箭头代表机器的规则：

· 处于状态 1 并且读入字符a 时，切换到状态 2；

· 处于状态 2 并且读入字符 a 时，切换到状态 1。

这让我们有足够的信息研究机器如何处理一个输入流。

· 这台机器从状态 1 开始。

· 这台机器只有从输入流读入字符 a 的规则，因此这是唯一能发生的事情。读取到 a 的时候，它会从状态1 切换到状态2。

· 当这台机器又读取到了一个 a 时，它会切换回状态 1。

一旦回到状态1，它又将开始重复自身，这就是这台机器的行为范围。我们可以认为当前状态的信息存在于机器内部——它像一个“黑盒”一样运转，并不会展现其内部工作状况——这台无聊的机器毫无用处，没有任何能观察到的输出。即使这台机器一直在状态1和状态2 之间切换，机器之外也没有一个人能看出来有什么事情在发生。因此在这种情况下，我们可能还要增加一个状态，这样就不用再为任何内部结构操心了。

3.1.2　输出

为了解决这个问题，有限自动机还有一个产生输出的基本方法。与现实中计算机复杂的输出能力相比这不值一提，我们只是把一些状态标记成特别状态，并且认为机器的单比特输出提供了当前是否处于特别状态的信息。对于这台机器，我们将状态2 作为特别状态，并在图中用双重的圆形表示它。

这些特定状态通常称为接受状态，表明这台机器对某个输入序列是接受还是拒绝。如果这台自动机从状态1 开始并读入一个a，它将会停留在状态2，这是一个接受状态，因此我们可以说这台机器接受字符串'a'。另外，如果它先读到一个a，然后又读取了另一个a，它将终止于状态1，这不是一个接受状态，所以这台机器拒绝字符串'aa'。事实上很容易看到，这台机器接受任何奇数个数的a 组成的字符串：'a'、'aaa'、'aaaaa' 都能被接受，但是'aa'、'aaaa' 和''（空字符串）会被拒绝。

现在有了稍有用一些的东西：一台机器，它能读取一个字符序列，并且提供一个“是/ 否”的输出，以表明这个序列是否已经被接受。公道地说，这个DFA（Deterministic Finite Automata）正在执行计算，因为我们可以向它提问——“这个字符串的长度是奇数吗？”——然后得到一个有意义的答案。它足以称为简单计算机了，并且我们可以将它的特性与一台现实中的计算机进行对比：

	真实计算机	有限自动机
持久存储	硬盘或者SSD	无
临时存储	RAM	当前状态
输入	键盘、鼠标、网络等	字符流
输出	显示设备、话筒、网络等	当前状态是否为一个接受状态（是/ 否）
处理器	能执行任何程序的CPU 核心	根据输入改变状态的硬编码规则

当然，这台自动机不做任何精细或者有用的工作，但是我们可以构造更复杂的自动机，让它拥有更多的状态并且能够读取多个字符。下面的自动机有三个状态，并且能够读取输入a 和b：

这台机器接受'ab'、'baba' 以及'aaaab' 这样的字符串，并且拒绝'a'、'baa' 和'bbbba'这样的字符串。实验表明，它只接受包含序列'ab'的字符串，因此仍然没有多大用，但至少展现了一定程度的精妙之处。本章后面我们将看到更实际的应用。

3.1.3　确定性

很明显，这种自动机具有确定性：不管它当前处于什么状态，并且不管读入什么字符，最终所处的状态总是完全确定的。只要满足下面两个约束，就能保证这种确定性。

· 没有冲突　不存在这样的状态：它的下一次转换状态因为有彼此冲突的规则而有二义性。（这意味着一个状态对于同样的输入，不能有多个规则。）

· 没有遗漏　不存在这样的状态：它的下一次转换状态因为缺失规则而未知。（这意味着每个状态都必须针对每个可能的输入字符有至少一个规则。）

综上所述，这些约束意味着对每一个状态和输入的组合，这台机器一定要恰好有一个规则。遵守这些确定性约束的机器有一个技术名称，就是确定性有限自动机（Deterministic Finite Automaton，DFA）。

3.1.4　模拟

确定性有限自动机是计算的抽象模型。我们已经画了一些示例机器的简图，而且思考了它们的行为，但是这些机器实际上并不存在，因此我们不能真正给它们一些输入然后看它们的表现。幸运的是，DFA 非常简单，我们很容易用Ruby 对其进行模拟，然后直接与它交互。

让我们通过实现一个规则集合对其进行模拟，并把这个规则集合称为规则手册（rulebook）：

class FARule < Struct.new(:state, :character, :next_state)
  def applies_to?(state, character)
    self.state == state && self.character == character
  end

  def follow
    next_state
  end

  def inspect
    "#<FARule #{state.inspect} --#{character}--> #{next_state.inspect}>"
  end
end

class DFARulebook < Struct.new(:rules)
  def next_state(state, character)
    rule_for(state, character).follow
  end

  def rule_for(state, character)
    rules.detect { |rule| rule.applies_to?(state, character) }
  end
end

这段代码为规则建立了一个简单的API：每个规则都有一个#applies_to? 方法（这个方法会返回true 或者false，指示这个规则是否可以在某个特定情况下应用），还有一个#follow 方法（在决定采用某条规则后返回关于机器应该如何改变的信息）。1 DFARulebook#next_state使用这些方法定位到正确的规则，并找到DFA 接下来的状态。

1这个设计足够通用，可以适应不同种类的机器和规则，因此在本书稍后情况更复杂的情况下我们还可以重用它。

通过使用Enumerable#detect，DFARulebook#next_state 的实现假定总是恰好有一个规则应用到给定的状态和字符上。如果可用的规则超过一个，那么只有第一个能起作用，其他规则都会被忽略；如果没有可以应用的规则，#detect调用会返回nil，并且在试图调用nil.follow 的时候模拟进程会崩溃。

这就是为什么这个类叫DFARulebook 而不是FARulebook 了：它只是在确定性约束满足的情况下才正确工作。

一个规则手册能够把许多规则封装到一个对象里，然后询问它接下来是什么状态：

>> rulebook = DFARulebook.new([
    FARule.new(1, 'a', 2), FARule.new(1, 'b', 1),
    FARule.new(2, 'a', 2), FARule.new(2, 'b', 3),
    FARule.new(3, 'a', 3), FARule.new(3, 'b', 3)
  ])
=> #<struct DFARulebook ...>
>> rulebook.next_state(1, 'a')
=> 2
>> rulebook.next_state(1, 'b')
=> 1
>> rulebook.next_state(2, 'b')
=> 3

此处我们面临一个选择，即如何把自动机的状态表示成Ruby 的值。重点在于能把这些状态区分开来：我们对DFARulebook#next_state 的实现需要能够比较两个状态，以判定它们是否相同，但并不关心那些对象是数字、符号、字符串、散列，还是Object 类的匿名实例。

在这种情况下，最清晰的方式是使用普通的Ruby 数字——它们能很好地匹配图中带编号的状态，因此我们就是这么做的。

有了一个规则手册之后，我们可以用它来构建一个DFA 对象，以跟踪它的当前状态，并且可以报告它当前是否处于接受状态：

class DFA < Struct.new(:current_state, :accept_states, :rulebook)
  def accepting?
    accept_states.include?(current_state)
  end
end

>> DFA.new(1, [1, 3], rulebook).accepting?
=> true
>> DFA.new(1, [3], rulebook).accepting?
=> false

现在可以写一个方法从输入中读取一个字符，然后查阅规则手册，再相应地改变状态：

class DFA
  def read_character(character)
    self.current_state = rulebook.next_state(current_state, character)
  end
end

为DFA 输入字符串，然后观察它输出的改变：

>> dfa = DFA.new(1, [3], rulebook); dfa.accepting?
=> false
>> dfa.read_character('b'); dfa.accepting?
=> false
>> 3.times do dfa.read_character('a') end; dfa.accepting?
=> false
>> dfa.read_character('b'); dfa.accepting?
=> true

一次只向DFA 输入一个字符有些不方便，所以添加一个方便的方法来读取输入的整个字符串：

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

现在可以向DFA 输入整个字符串了，而不再只是分别传入单个字符：

>> dfa = DFA.new(1, [3], rulebook); dfa.accepting?
=> false
>> dfa.read_string('baaab'); dfa.accepting?
=> true

一旦DFA 获得了一些输入，它就可能不再处于起始状态了，因此我们不能再次使用它检查输入的一个新的完整序列。这意味着要从头创建它——像以前那样使用同样的起始状态、接受状态和规则手册——每当想要检查它是否接受一个新的字符串时。我们可以在一个对象里封装它的构造参数来避免手工执行这一操作，这个对象表示设计出来的特定DFA，只要我们想要检查是否可以接受一个新的字符串，就靠此对象自动地构建那个DFA的一次性实例：

class DFADesign < Struct.new(:start_state, :accept_states, :rulebook)
  def to_dfa
    DFA.new(start_state, accept_states, rulebook)
  end

  def accepts?(string)
    to_dfa.tap { |dfa| dfa.read_string(string) }.accepting?
  end
end

#tap 方法对一个代码块求值，然后返回调用它的对象。

DFADesign#accepts? 使用DFADesign#to_dfa 方法创建一个DFA 的新实例，然后调用#read_string? 把它放到一个接受态或者拒绝态里：

>> dfa_design = DFADesign.new(1, [3], rulebook)
=> #<struct DFADesign ...>
>> dfa_design.accepts?('a')
=> false
>> dfa_design.accepts?('baa')
=> false
>> dfa_design.accepts?('baba')
=> true