最简单的计算机之有限自动机

[AlexiaChen]

---

title: 最简单的计算机之有限自动机
date: 2018-10-15 20:30:48
tags:
- 程序语言理论
- 计算理论

简单是终极的复杂 -- 达 芬奇

前言

其实这算是计算理论的第二个章节，第一个章节可以去看我之前写的文章----《程序的含义》。

追求简单是人类内心的本性使然，看上去好像没有太多修饰，当你仔细揣摩，你会发现，最精华的理论已经融入每个角落，越是简单的东西，其实越难吧空，需要经过千锤百炼。

现代计算机具有强大的计算能力，但是正是由于其强大，所以伴随着过多的复杂性。我们很难理解一台计算机多个子系统的全部细节，更别说理解这些子系统如何互相协作从而构成整个系统了。这些复杂性使得对真实的计算机的能力与行为进行直接推导显得不切实际，此时计算机的简化模型就显得非常有用。简单的模型只提取出真实计算机中令人感兴趣的特性，它可以帮助人们建立对计算完整的认知。

接下来，我们会逐步揭开什么是计算，最后分析这样简单的模型所能达到的计算极限。

确定性有限自动机

现实中，计算机通常有大量的RAM和DISK，还有许多I/O设备（键盘等），还有CPU。有限状态机也被称作有限自动机，这是一个极简的计算机模型。它为了简单，抛弃了RAM DISK等这些特性。

状态 规则 输入 输出

有限状态机你可以把它看作是一个抽象机器，它拥有一些可能的状态，能跟踪到自己当前具体处于其中的一个状态。注意，它没有键盘等这些接口，它只有一个抽象接口，就是一个来自外部的信息输入流会被它逐个读取，并随着这些信息的输入，自动转移状态。

以下是一个有限状态机的图示：

至于状态机怎么看，我就不过多介绍了。如果学过《编译原理》的词法分析的章节，一定会接触到的。

• 该机器有两个状态， 1和2
• 该机器的输入字符集合为{a，b}
• 该机器的初始状态是1

该机器会根据读到的字符来决定转移的状态，它不停的接受a，b在状态1和2之间来回切换，简直没完没了了。它像一个黑盒子一样运行，谁也不知道发生了啥，机器外面没人知道发生了什么，所以机器要有个输出，我们才知道最终的结果，有了结果，机器就停止运行了，相当于这个函数才有了输出，有输入必然要有输出，不然没意义。 所以我们需要为这台机器增加一个终止状态，以表示运行结束，产生输出。

我们暂且把状态2标记为终止状态，当然如果用在词法分析理论上也可以被称为接受状态，表明机器对某个序列是接受还是拒绝。修改好的状态机图示如下：

红色就表示终止状态。当然，正规点的自动机终止状态是画两个圆表示终止，我这里图个简便，请谅解下。

好了，我们来分析下。

上图的自动机初始化状态为1, 当读入一个字符a的时候，它会转移到状态2，这是一个终止状态，所以我们可以认为这自动机接受了字符串“a”。如果它又读取了一个字符b，状态又转移到了1,这不是终止状态，所以自动机不接受字符串“ab”，也就是拒绝了“ab”。所以很容易可以推理出来，自动机接受“a”，“aba”，“ababa”这样的字符串。如果把图示下面的字符b也换成a。那么自动机接受“a”，“aaa”，“aaaaa”这样奇数的a组成的字符串，拒绝“”，“aa”，“aaaa”这样偶数个字符a组成的字符串或空字符串。这台自动机就可以判断a组成的字符串是技术还是偶数，是足以称为最简单的计算机了。

当然，我们可以构造更复杂的自动机，我就不打算构造了。

确定性

显然，如果了解自动机概念的人，就知道之前所提到的自动机都是具有确定性，也就是说，无论它处于什么状态，并且无论读入什么字符，它最终所处的状态总是完全确定的。这样的确定性有2种约束条件：

• 不存在二义性，也就是说一个状态对于同样的输入，它不能有多个规则

• 每个状态都必须针对每个可能的输入字符至少有一个规则

具有这种确定性的自动机专业点叫确定性有限自动机（Deterministic Finite Automaton，DFA）。

用程序语言来实现DFA

DFA是一种抽象机器，也可以被认为是一种解释器，这种机器很容易用软件来模拟。

首先，需要定义一个规则集合RuleSet。

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}>"
  end
end

class DFARuleSet < 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) } # find first if
  end
end

每个规则用一个FARule来表示，都有一个applies_to? 这样的API来判断某些输入情况下是否可以apply。DFARuleSet表示规则集合，相当于FARule类的一个容器，存放多个FARule。

好的，现在可以构造一个规则集合了：

=begin
#<struct DFARuleSet rules=[#<FARule 1 --a--> 2>, #<FARule 1 --b--> 1>, #<FARule 2 --a--> 2>, 
#<FARule 2 --b--> 3>, #<FARule 3 --a--> 3>, #<FARule 3 --b--> 3>]>
=end
rules = DFARuleSet.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)
])

# 测试DFARuleSet类

# => 2
rules.next_state(1,'a')
# => 1
rules.next_state(1,'b')
# => 3
rules.next_state(2,'b')

到这里，是否能根据这个规则集合画出对应的DFA的图呢，这是可以的。下图就是以上RuleSet对应的自动机

不过，这台自动机没有终止状态，还不完整，所以我们要编写一个DFA的类的表示DFA来配置RuleSet和初始状态，终止状态，加入读取字符流的接口，并模拟抽象机器的运行，这样就灵活了。计算机科学很重要的一点就是抽象思维，分离变化与不变化。是不是跟上一章讲解语义的一样呢？其实都相当于一台解释器。

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

  def read_char(character)
    self.current_state = ruleset.next_state(current_state,character)
  end

  def read_string(str)
    str.chars.each do |character|
      read_char(character)
    end
  end  
end

# 测试下DFA

# => true
DFA.new(1,[1,3],rules).accepting?

# => false
DFA.new(1,[3],rules).accepting?

之后，为了更加方便，我们构造一个可以创建DFA的工厂类：

class DFAMaker < Struct.new(:start_state, :final_states, :ruleset)
  def make_dfa
    DFA.new(start_state,final_states,ruleset)
  end
  
  def accepts?(str)
    make_dfa.tap { |dfa| dfa.read_string(str) }.accepting?
  end
end

# => false
DFAMaker.new(1,[3],rules).accepts?('a')

# => false
DFAMaker.new(1,[3],rules).accepts?('baa')

# => true
DFAMaker.new(1,[3],rules).accepts?('babab')

# => true
DFAMaker.new(1,[2],rules).accepts?('aaaa')

# => false
DFAMaker.new(1,[1],rules).accepts?('a')

# => true
DFAMaker.new(1,[1],rules).accepts?('b')

非确定性有限自动机

之前的确定性有限自动机（DFA）理解和实现起来都很简单，那是因为DFA与我们熟悉的机器非常相似。

在去除了一台真实的计算机的所有复杂性之后，我们有机会使用一些不太常见的思想去进行探索，这将让我们离本质会更进一步。

一种探索方式是去除我们现在所有的假设和约束。首先，确定性约束似乎是个限制，因为可能我们有些时候并不关系每个状态上每个可能的输入，那么为什么不能忽略不关心的字符处理规则，并假设当异常发生时这台机器能进入到一个通用的失败状态呢？ 那好，我们再进一步放宽要求，如果允许这台自动机拥有对立的规则，那么就会导致机器有多个执行路径，这又意味着什么？

现在我们将要探索这些想法，需要对DFA的能力稍微做调整一下，看看有没有新的可能。

非确定性

假设我们想要一台自动机，它能接受由a和b组成的第三个字符是b的任意字符串，那么很容易想到以下DFA的图示：

以上的DFA处于状态3的时候，一旦读取到b就终止了，如果后面还有输入字符，就不停的循环进入终止状态5，反正目的达到了，只要是第三个字符是b的任意字符串就可以了，但是状态3读到了a字符，那么之后无论遇到什么输入，直到字符流读取完成，字符串也不能被该DFA识别了。

到这里你发现DFA好强大呀，好像没什么不能完成的任务（对于特定字符串识别）。但是你错了，现在我提出一个问题，请设计一台自动机，满足识别倒数第三个字符是b的任意字符串，请问该怎么设计？（这里先别往下看，留一段时间在纸上画画图）。

经过一段时间的思考，有人会发现这似乎会很困难，因为上面的DFA读取正数第三个的字符是b的时候保证在状态3，但是如果是倒数第三个就困难了，自动机很难预先知道什么时候能读到倒数第三，因为在整个字符流读取完成之前它不知道这个字符串有多长。现在我来告诉你，几乎不存在一台DFA能识别这样的需求的字符串。

这时候要加强DFA的能力就需要放宽要求，把它改了，把确定性改成非确定性，换一个概念得了，叫非确定性有限自动机（NFA）。

NFA就是对于每个状态特定的输入结果下，跳转的下一个状态都是不确定的。这个不确定的概念给自动机带来了更加强大的能力。这样就可以很轻松设计以下一台NFA：

查看以上NFA，对于状态1来说，接受一个字符b，它有可能保持在状态1，也可能跳转到状态2。也就是，对于状态1来说，字符b的输入导致的结果是不确定的。

用以上NFA来识别字符串“baa”，读取完字符串之后，最终状态可能停留在状态1，也可能停留在状态4接受态。所以用NFA来识别字符串就要遍历所有可能的状态执行路径，只要存在一种路径能达到终止态，那么该字符串就被这台NFA所接受识别。哈，这么来看有点暴力搜索了，但是没办法，因为我们现实世界的物理计算机就是确定性的计算机，要模拟非确定性只有这样的办法了

这样的暴力方式很容易可以看到两种实现，一个是采用递归，一种是采用线程并行，但是这两种实现都有点复杂和低效。

我们可以采用一种更简洁高效的模拟，模仿DFA的模拟实现。

很简单，最开始与DFA类似，也要创建一个RuleSet来存放规则集合。它与DFA不一样的是，在某个状态时接收相同的输入，可能跳转转移的状态不一致，也就是可能下一个状态是多个可能，所以需要引入编程语言提供的集合（Set）的概念来给下一个状态集去重。

require 'set'

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}>"
  end
end

class NFARuleSet < 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) } # select * where 
  end
end

好的，现在我们来用以上的Ruby类来定义上一副图示所表示的NFA：

ruleset = NFARuleSet.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)
])

# => #<Set: {1, 2}>
ruleset.next_states(Set[1], 'b')
# => #<Set: {1, 3, 4}>
ruleset.next_states(Set[1,2,3], 'a')
# => #<Set: {1, 2, 4}>
ruleset.next_states(Set[1,3], 'b')

对ruleset的定义能看得出来吗？ next_states的输入参数是当前状态集合，第二个参数是当前状态的输入数据，返回值是接收输入数据后返回的下一个状态集合。

好的，再下一步就是通过程序来模拟手工的NFA运行，与DFA本质上并没有区别：

class NFA < Struct.new(:current_states, :final_states, :ruleset)
  def accepting?
    (current_states & final_states).any?       # set intersection operation is empty?
  end

  def read_char(character)
    self.current_states = ruleset.next_states(current_states,character)
  end

  def read_string(str)
    str.chars.each do |character| 
      read_char(character)
    end
  end
end

class NFAMaker < Struct.new(:start_state, :final_states, :ruleset)
  def make_nfa
    NFA.new(Set[start_state], final_states, ruleset)
  end
  
  def accepts?(str)
    make_nfa.tap { |nfa| nfa.read_string(str) }.accepting?
  end
end

nfa = NFAMaker.new(1, [4], ruleset)
# => true
nfa.accepts?('bab')
# => true
nfa.accepts?('bababab')
# => false
nfa.accepts?('babababa')
# => true
nfa.accepts?('bababababbbbbb')

哈哈，以上代码最终实现的效果与NFA的的图示所达到的效果一样了，能接受"bab"，“baa”这样倒数第三个字符是'b'字符的字符串。

自由移动

上一小节中，我们看到了对确定性这个约束条件的放宽给设计NFA的方法带来了一定的表达能力，为了再次提高表达，是否还可以放松哪些条件呢？

回到DFA的层面，很容易设计一台DFA，这个DFA能接受字符a组成的字符串长度是2的倍数（“aa”, "aaaa", ......）。

但是，如何设计一台机器，让这台机器既能接受长度是2的倍数也能接受是3的倍数的字符串呢？ 由于之前了解过NFA的概念，于是有人可能随手就实现了以下一台NFA：

以上这台NFA确实能接受"aa" "aaaa" "aaa" "aaaaaa"这样的字符串，满足要求。但是仔细一看，其实它也能接受"aaaaa" 这样不满足设计要求的字符串。我靠，不符合设计啊。如果不经过严密思考，一旦NFA比较复杂，那么这种错误一般比较难发现。怎么办呢？

其实已经很接近真相了，最主要是因为这一台NFA要满足2个条件，这两个条件写在一起了，其实我们可以把这两个条件，根据每个条件写出对应的DFA，然后把DFA组合在一起形成一个规模大点的NFA机器。

我们把这种组合特性叫做自由移动，这个特性就是能让NFA在多组状态中做选择的。我们把自由移动这种特性用没有转移输入的箭头来表示：

上面这台NFA，但如果在当前是状态1。那么它的当前状态就既是2也是4的状态。也就是说，这台NFA的初始状态集合是[1,2,4]。状态1流转只能到2或4，这样就分叉了，根据箭头是回不去状态1的，这样2台DFA各司其职。

那么如果用Ruby怎么模拟NFA中的自由移动呢？ 其实就在RuleSet的规则集合中定义一个无输入并且自由流转的规则。 好的，我们根据这点来根据上图所示的NFA，设置它的规则：

ruleset = NFARuleSet.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)
])

# => #<Set: {2, 4}>
ruleset.next_states(Set[1], nil)

状态1在无输入的情况下的下一个状态集合就是[2,4]。然后需要在RulSet的类中添加一个方法来计算一个状态集合的自由移动，这个方法同样返回一个状态集合：

class NFARuleSet
  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

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

然后，要模拟当前状态的自由移动，重写NFA类中的current_states：

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

这样的意图是，确保NFA当前可能的状态总是通过自由移动流转到任何可能的状态。这就让访问当前状态透明了，之前的代码几乎不用改动。好了，现在可以用之前的NFAMaker构造出一个支持自由移动的NFA了，并且按照上图的NFA设计图，并确保代码可以正确工作了：

nfa = NFAMaker.new(1, [2, 4], ruleset)
# => true
nfa.accepts?('aa')
# => true
nfa.accepts?('aaa')
# => false
nfa.accepts?('aaaaa')
# => true
nfa.accepts?('aaaaaa')

看运行结果，恩，与设想中的一样。能接受2或3的倍数，并且不会出错了。

模拟自由移动比现象中简单，它在非确定的基础上给了设计者额外的设计自由。当然从自动机理论的角度看，这文章中的很多名词并不专业，有限自动机读取的字符一般叫符号（Symbol），状态之间移动的规则叫做转移（transition），组成一台机器的规则集合叫做转移函数,表示空字符串的数学符号是希腊字母ε，能自由移动的NFA称为NFA-ε，自由移动一般叫ε转移。

如果你学过编译原理的国外教材，在讲状态机的时候就会接触到这些，比如把正则表达式通过NFA写出来，就会用到ε转移来组合各种状态机，然后通过子集构造法把NFA规约成DFA。 后面我会讲到有限状态机与正则表达式是等价的，相当与正则表达式是有限自动机的文本表示出来的语言（正则语言，有时候也叫正规语言），而有限状态机是正则语言的解释器。所以当你想从底层实现正则表达式引擎的话，无论如何也绕不过有限状态机理论的。当然有些高级做法，并没有把正则表达式翻译成自动机执行，但是我这里不想过多涉及这样工业界的高级解释器技巧，这已经偏离文章宗旨。

正则语言

正则语言也叫正则表达式，这是一个很简单的语言，正因为太简单了，所以在表达一些复杂模式匹配的时候语言会有些晦涩。但是它的单个规则很简单，都是通过简单的规则组合起来用的。这个子章节，我需要用Ruby构造的NFA一步一步来构建最简单的正则表达式的解释器。

（To be contined）