有穷自动机

有穷自动机在本质上是与状态转换图类似的图，但有一些不同：

1. 有穷状态机是识别器(recognizer)，它们只能对每个可能的输入串简单地回答“是”或者“否”。
2. 有穷状态机又分为不确定的和确定的有穷状态机。

不确定的有穷状态机

• NFA组成

不确定的有穷状态机(NFA)由以下几个部分组成：

1. 一个有穷的状态集合S。
2. 一个输入符号集合Σ，即输入字母表(input alphabet)。
3. 一个转换函数(transition function)，它为每个状态和每个符号都给出了相应的后继状态集合。
4. S的一个状态被指定为开始状态。
5. S的一个子集被指定为接受状态的集合。

• 转换图

不管是NFA还是DFA，我们都可以将它表示为一张转换图(transition graph)。图中的节点表示状态，带有标号的边表示自动机的转换函数。这个图与状态转换图十分相似，但是有些区别如下。

1. 同一个符号可以标记从同一个状态出发到达多个目标状态的多条边。
2. 一条边的标号可以是空符号串ε。

转换表

我们也可以将一个NFA表示为一张转换表(transition table)，表的各行对应状态，各列对应于输入符号和ε。

转换表的优点是：我们能够很容易地确定和一个给定状态和一个输入符号相对应的转换。
转换表的缺点是：如果输入字母表很大，且大多数状态在大多数输入字符上没有转换的时候，转换表需要占用大量空间。

自动机中输入字符串的接受

由一个NFA定义(或接受)的语言是从开始状态到某个接受状态的所有路径上的标号串的集合。

例如正则表达式(a|b)*abb及其等效NFA所定义的语言，即所有来自字母表{a,b}且以abb结尾的串的集合。

确定的有穷自动机

确定的有穷自动机(DFA)是不确定有穷自动机的一个特例。

1. 没有输入之上的转换动作。
2. 对每个状态s和每个输入符号a，有且只有一条标号为a的边离开s。

NFA抽象地表示了用来识别某个语言中的串的算法，而相应的DFA则是一个简单具体的识别串的算法。

在构造词法分析器的时候，我们真正实现的是DFA。

（END）