第三章：有限自动机

[murphywuwu]

• [x] 3.1 确定性有限自动机
  • [x] 3.1.1 状态、规则和输入
  • [x] 3.1.2 输出
  • [x] 3.1.3 确定性
  • [x] 3.1.4 模拟
• [x] 3.2 非确定性有限自动机
  • [x] 3.2.1 非确定性
  • [x] 3.2.2 自由移动
• [x] 3.3 正则表达式
  • [x] 3.3.1 语法
  • [x] 3.3.2 语义
  • [x] 3.3.3 解析
• [x] 3.4 等价性

[murphywuwu]

有限自动机

有限自动机没有持久化的存储并且几乎没有RAM。它只是一台小机器，拥有一些可能的状态，并能够跟踪到自己当前具体处于其中的那个状态---试着把它看成一台RAM只够存储一个值的计算机，只有一个外部的字符输入流可以一次读取一个字符。

每台有限自动没有通用的CPU执行任意程序，而是硬编码了一些规则集合，以决定在相应的输入下如何从一个状态切换到另一个状态。

• 状态总数是有限的
• 任一时刻，只处在一种状态中
• 某种条件下，会从一种状态转换到另一种状态

确定性有限自动机:DFA(Deterministic Finite Automata)

对于不管它处于什么状态，并且不管读入什么字符，最终所处的状态总是完全确定的。只要满足下面两个约束，就能保证这种确定性

• 唯一性
• 存在性

这意味着每个状态和输入的组合，这台机器恰好有一个规则。

[murphywuwu]

DFA对象

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

[murphywuwu]

非确定性有限自动机:NFA

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

一台DFA按照可能性而不是确定性工作：我们根据可能发生的而不是将要发生的来讨论它的行为。

在确定计算机上模拟一台NFA，关键是找到一种方法探索出这台机器所以可能的执行。

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

还有一个策略就是采用并行的方式模拟所有可能：每当机器有超过一条规则可以遵守时就创建新线程，并把需要模拟的NFA复制过去以便复制的每一份都能尝试一条新规则，然后观察它的结果。所有这些线程都能同时执行，每个都从它自己的输入字符串副本中读取。如果任何一个线程让机器读取了整个字符串，并且停止于一个接受状态，那么可以说这个字符串已经被接受了

[murphywuwu]

NFA的接受态

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

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

[murphywuwu]

自由移动

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

在这种情况下，"机器从状态1开始"的真正意思是：在没有读取任何输入之前，它可能处于状态1，2，4

[murphywuwu]

正则表达式

把任何正则表达式转成一个等价的NFA是可能的---每一个正则表达匹配的字符串都能被这台NFA接受，反过来也一样---把字符串输入给一台模拟的NFA看它是否能被接受，从而判断是否与正则表达式匹配。

[murphywuwu]

我们现在需要知道如何把每个语法类的实例转换成NFA。转换起来最简单的类是Empty，应该总是把它转换成一个状态的NFA。这个NFA只接受空字符串。

类似地，我们应该把任何单字符的模式转换成只接受包含那个字符的、单字符串的NFA。下面是模式a的NFA。有一个起始状态和一个可接受状态，NFA在起始状态时接受字符串a会转换到可接受状态。

每一个NFA都能有它自己独一无二的状态，以便把小的机器组合成大的机器，而不会意外的把它们的状态进行归并。

[murphywuwu]

既然我们已经知道如何把简单的Empty和Literal正则表达式转换成NFA了，那对Concatenate(串联)、Choose(选择)和Repeat(重复)也需要类似的进行转换。 从Concatenate开始：如果有两个已经知道如何转换成NFA的正则表达式，那么如果构造一个NFA表示这些正则表达式的串联呢？举个例子，假如能把当个字符的正则表达式a和b转换成NFA，那么怎么把ab转换成一个NFA呢？

• ab转换成的NFA只包含一个接受态:第二个NFA的接受状态
• ab转换成的NFA的起始态：第一个NFA的起始状态
• ab转换成的NFA的路线图：把两个NFA按顺序用自由移动把它们连接在一起连接到一起，如上图，因此所有状态到状态转换的路线图规则为两台NFA的所有规则，以及一些额外的自由移动，可以把第一台NFA旧的接受状态和第二台NFA旧的起始状态连接起来

[murphywuwu]

使用同样的策略把Choose表达式转换成一台NFA。在最简单的情况下，正则表达式a和b的NFA能结合起来构造成正则表达式a|b的NFA，方法是增加一个新的起始状态并使用自有移动把它与两台原始机器的起始状态连接起来

[murphywuwu]

把Repeat表达式转换成NFA，如图所示

• 从它的接受状态到开始状态增加一个自由移动，这样它就可以与多于一个'a'匹配了

• 增加一个新状态可自由移动到旧的开始状态，并且使其作为接受状态，这样它就可以匹配空字符串了

[murphywuwu]

/(a(|b))*/

[murphywuwu]

[murphywuwu]

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

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

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

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

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

这个DFA比我们开始的NFA多出一个状态，而且对于一些NFA，这个过程会产生比原始机器的状态更少的DFA。但在最坏情况下，一台又n个状态的NFA可能需要一台有2^n个状态的DFA，因为n个状态总共有2^n个可能组合

[murphywuwu]

下面我们用Ruby实现这个NFA到DFA的转换。策略是引入一个新的NFASimulation，用来收集NFA模拟的信息然后把这些信息汇总到一台DFA。