1、第二章有限自动机Date 1计算机科学的数学基础2. 1 有限自动机的定义与构造 有限自动机（ Finite AutomataFA ）或称为有穷状态的机器，由一个有限的内部状态集和一组控制规则组成。 在计算机科学中，可以找到许多有限状态系统的例子，如计算机本身也可以是认为是一个有限状态系统。 有限自动机与正规文法和正规式有着非常密切的关系，它们的描述能力是相同的。 Date 2计算机科学的数学基础例 2.1 构造一个有限自动机 M0，它能识别出除以 3余2的二进制数。解：用 V3(x)来表示二进制数 x除以 3的余数，例如， V3 (100) 1, V3 (1011) 2，设输入符号串为 w
2、a1a2 an，其中 ai 0, 1， 0in。显然，对于每一个 i， 0in，自动机读入符号串 a1a2 ai后，二进制数 a1a2 ai除以 3的余数 V3(a1a2 ai)必然为0、 1、 2之一，不可能有其它情况。因此可知，在自动机 M0中只需要采用三个状态来分别表示上述的三种情况即可。令自动机 M0中有状态 q0、状态 q1和状态 q2分别表示余数为 0、 1和 2的情况。 Date 3计算机科学的数学基础状态之间的转换 当 M0读完符号串 a1a2 ai后又读到符号 ai+1时，新符号串 a1a2 ai ai+1除 3的余数与原符号串 a1a2 ai除 3的余数之间显然有：V3(a
3、1a2 ai ai+1) 2*V3(a1a2 ai) + ai+1(mod 3) 101 01 0图 2. 1 有限自动机 M0q0 q1 q2Date 4计算机科学的数学基础自动机的抽象模型 可以将有限自动机抽象地描述成如图 2.2所示的模型，该模型由一条无穷长度的输入带、一个读头和一个有限控制器组成。 图 2.2 有 限自动机读头有限状态控制器0 1 0 1 1 0 输入带Date 5计算机科学的数学基础确定的有限自动机定义 2. 1 一个确定有限自动机 (DFA)M是一个五元组M = (S, , f, s0, Z)其中： 是有穷字母表 ,它的每一个元素称为一个输入符号； S是有限状态集，
4、它的每一个元素称为一个状态； f是转换函数，是从 SS上的一个单值映射，即 f(p, a) q， q称为 p的后继状态； s0 S是一个 唯一的初始状态 ； Z S是一个 终止状态集 。 对于一个给定的属于该自动机的状态和一个属于该自动机字母表 的字符，它都能根据事先给定的转移函数转移到下一个 唯一确定的 状态（这个状态可能是先前那个状态）。定义 2. 2 DFA M所接受的符号串的集合称为 DFA M所接受的语言，记为 L(M)，即：L(M) w | f(s0, w) Z， w * Date 6计算机科学的数学基础不确定的有限自动机 (NFA)定义 2. 3 一个不确定有限自动机 M是一个五
5、元组M ( S, , f, S0, Z)其中： 是有穷字母表 ,每一个元素称为一个输入符号； S是有限状态集，每一个元素称为一个状态； f是转换函数 : S (S)上的映射 (S)是 S的幂集 )，即 f(p,a) q1,.,qk，表示当前的状态为 p，输入符号为 a时，则转换到的状态是一个状态集； S0 S是 初始状态集 ； Z S是 终止状态集 。 对于一个给定的属于该自动机的状态和一个属于该自动机字母表 的字符，它将根据事先给定的转移函数转移到下一个 不确定的 状态（因为转换到的状态是一个状态集）。Date 7计算机科学的数学基础DFA与 NFA的比较 DFA的转换函数是从 S到 S上的
6、一个单值映射。 NFA的转换函数是从 S到 (S) (S的幂集 )的映射，而不是到 S的映射，即一个状态可转换到的后继状态是一个状态集合 (可能是空集 )，而不是单个状态。 NFA有一个初态集 , DFA的初态是唯一的。 DFA和 NFA都正好识别正规集。 它们之间存在着时空权衡问题 , DFA识别速度快，占用空间大， NFA识别速度慢，占用空间小。 Date 8计算机科学的数学基础非确定有限自动机的推广 将具有 动作的非确定有限自动机定义为五元组 ( S, , f, S0 , Z)，其中除转移函数 f外的分量的定义如同定义 2. 3，但转移函数 f是如下映射： S ( ) (S) f(q, ) q。 若 NFA的某些状态既是初态又是终态，则空字 可为该 NFA M所接受。 具有 动作的 NFA并不增加 NFA接受语言的能力。 Date 9计算机科学的数学基础 定理 2. 1 对任何一个具有 动作的 NFA M ，一定存在一个不具有 -转移的 NFA M，使得 L(M) L(M)。 其证明的基本思想是去掉 弧。 DFA可视为 NFA的一个特例，其中：(1) 没有一个状态有 转换；(2) 对每一个状态 s和输入符号 a，最多只有一条标记为 a的弧离开。 对于任何两个有限自动机 M和 M，如果L(M) L(M)，则称 M和 M是等价的 。 Date 10计算机科学的数学基础
