2.3 有穷自动机
前面在介绍词法分析程序的手工实现时引入了状态转换图，为了讨论词法分析器的自动生成，需要将上述状态图的概念形式化，即引入有穷自动机。有穷自动机分为确定的有穷自动机和非确定的有穷自动机。
2.3.1 确定的有穷自动机
定义2.9（确定的有穷自动机（Deterministic Finite Automaton，DFA）） 一个确定的有穷自动机M是一个五元式M = （Q，∑，δ，q0，F），其中：
1）Q是一个有穷状态集，它的每一个元素称为一个状态。
2）∑是一个输入字母表，它的每个元素称为一个输入字符。
3）δ是从Q×∑到Q的单值部分映射，称为状态转换函数，δ(p，a)=q表示当前状态为p，输入符号为a时，自动机将转换到下一个状态q，q称为p的一个后继。
4）q0∈Q是唯一的初态（又称为开始状态）。
5）F?Q，称之为终止态集，其可为空。
之所以称为确定的有穷自动机，是因为δ为一个单值映射。DFA可用状态转换图来表示，假定DFA M含有m个状态和n个输入字符，那么，与之相对应的状态转换图含有m个状态结点，每个结点最多含有n条箭弧射出，且每条箭弧用∑上的不同输入字符来作标记。状态转换图在计算机上有不同的实现方法，最简单的实现方法是转换表（转移矩阵），其行表示状态，列表示输入字符，表的内容对应相应的状态转移函数值。
例2.20 DFA M=({0, 1, 2}, {letter, digit, -, other}, δ, 0, {2})，其中，δ定义如下：
δ(0, letter)=1 δ(0, -)=1 δ(1, letter)=1
δ(1, dight)=1 δ(1, -)=1 δ(1, other)=2
其状态转移矩阵见表2-2，所对应的状态转换图如图2-6所示。
不难看出，字符串w被DFA M接受的充分必要条件是在M的状态转换图中存在一条从开始状态到某一个终态的有向路，该有向路上所有弧上的标记符连接成的字等于w。若M的初态结点同时又是终态结点，则空字ε可为M所识别（接收）。DFA M所识别的字的全体称为其所识别的语言，记作L(M)。例2.20中自动机所识别的语言即为所有以字母或下划线开头的字母、数字和下划线组成串的集合。
2.3.2 非确定的有穷自动机
若状态转换函数是一个多值函数，且输入可允许为ε，则有穷自动机是不确定的，即在某个状态下，对于某个输入字符存在多个后继状态。
定义2.10（非确定的有穷自动机 (Non-deterministic Finite Automaton，NFA)） 一个非确定有穷自动机M是一个五元式M=(Q，∑，δ，q0，F)，其中：
1）Q是一个有穷状态集，它的每一个元素称为一个状态。
2）∑是一个输入字母表，它的每个元素称为一个输入字符。
3）δ：Q×(∑?∪?{ε})→2Q，对?(q，a) ∈Q×(∑??∪?{ε})，δ(q，a)={p1，p2，…，pm}表示M在状态q读入字符a，可以选择地将状态变成p1或者p2或者pm。
4）q0∈Q是唯一的一个初态。
5）F?Q，F称为终止态集，其可为空。
同样，NFA可用状态转换图来表示。假定NFA M含有m个状态和n个输入字符，那么这个图含有m个状态结点；同一个字符或者空字可能出现在同一状态射出的多条弧上。对于∑?*中的任何字α，若存在一条从某一初态到某一终态的道路，且这条路上所有弧上的标记符连接成的字（忽略那些标记为ε的字）等于α，则称α为NFA M所识别(接收)。若M的初态结点同时又是终态结点，或者存在一条从某一初态到某一终态的ε道路，则空字ε可为M所识别（接收）。NFA M所识别的字的全体称为其所识别的语言，记做L(M)。
例2.21 NFA M=({0, 1, 2}, {a, b}, δ, 0, {2})，其中，δ定义如下：
δ(0, a)={0, 1} δ(1, b)={1, 2}
其状态转移矩阵见表2-3，所对应的状态转换图如图2-13所示。
该非确定自动机所识别的语言为{ambn | m，n≥1}。
例2.22 NFA M=({0, 1, 2, 3, 4, 5, 6, 7}，{+, -, digit, ., E}, δ, 0, {ε})，其中δ定义如下：
δ(0, digit)={1} δ(1, digit)={1}
δ(1, .)={2} δ(1, E)={4}
δ(1, ε)={7} δ(2, digit)={3}
δ(3, digit)={3} δ(3, E)={4}
δ(3, ε)={7} δ(4, +)={5}
δ(4, -)={5} δ(4, digit)={6}
δ(5, digit)={6} δ(6, digit)={6}
δ(6, ε)={7}
其状态转移矩阵见表2-4，所对应的状态转换图如图2-5所示，该非确定自动机所识别的语言为无符号常数组成的集合。
2.3.3 NFA到DFA的转化
由定义可知DFA是NFA的特例，而对于每个NFA M存在一个DFA M'，使得 L(M)= L(M')，亦即DFA与NFA描述能力相同。下面介绍一种将NFA转化成等价的DFA的方法，该方法称为子集构造法。其基本思想是：
1）DFA的一个状态对应NFA的一个状态集合。
2）读了输入a1 a2 … an后，NFA能到达的所有状态为s1、s2、…、sk，则DFA读了输入a1 a2 … an后到达状态{s1，s2，…， sk}。
在未介绍该方法之前，首先介绍与状态集合I相关的几个函数。
定义2.11（状态子集I的ε-闭包） 设I是有穷自动机M的状态集的一个子集，定义I的ε-闭包ε-closure(I)为：
1）若s∈I，则s∈ε-closure(I)。
2）若s∈I，则从s出发经过任意条ε弧而能到达的任何状态s'都属于ε-closure(I)。
即ε-closure(I)=I?∪?{s'|从某个s∈I出发经过任意条ε弧能到达s'}。
定义2.12（状态子集I的Ia） 给定一个有穷自动机M=(Q，∑，δ，q0，F)，设a是∑中的一个字符，I是Q的一个子集，定义
Ia = ε-closure(J)
其中，J为从I中的状态出发经过一条a弧而到达的状态集合。
例2.23 图2-14为一个NFA所对应的状态转换图，已知I=ε-closure({1})={1，2}，试求Ia。
解：由定义2.12可得，从状态I中的状态1或状态2出发经过一条a弧而能到达的状态集J为{5，4，3}。
再由定义2.11可得Ia= ε-closure(J)= ε-closure ({5, 4, 3})={5, 4, 3, 6, 2, 7, 8}。
下面给出将NFA转化成等价的DFA的子集构造法。
算法2.5 从NFA到DFA的子集构造法
输入：一个NFA M=(Q, ∑, δ, q0, F)
输出：一个与NFA M等价的DFA D
步骤：
1.构造一张转换表，其第一列为状态子集I，对不同的a (a∈∑)在表中单设一列Ia。
2.置表的第一行第一列为ε-closure({q0})。
3.根据第一列中的I为每一个a求其Ia并记入对应的Ia列中，如果此Ia不同于第一列已存在的所有状态子集I，则将其填入后面空行的第一列。
4.重复步骤3直至所有状态子集Ia全部出现在第一列为止。
5.重新命名该表中的每一状态子集，得到一个新的状态转换矩阵，该矩阵唯一刻画了一个确定的有穷自动机D，它的初态是子集ε-closure({q0})所对应的状态，它的终态是含有原终态集F中元素的子集所对应的状态。
例2.24 利用子集构造法将例2.22中的NFA转化为等价的DFA。
解：用子集构造法将例2.22的NFA M确定化为表2-5。对表2-5中的所有子集重新命名，得到如表2-6所示的状态转换矩阵。与表2-6相对应的状态转换图如图2-15所示，该图所对应的DFA即为所求。
表2-5 例2.24的状态转换表
I I+ I- Id I. IE I I+ I- Id I. IE
{0} — — {1, 7} — — {3，7} — — {3, 7} — {4}
{1，7} — — {1, 7} {2} {4} {5} — — {6, 7} — —
{2} — — {3, 7} — — {6，7} — — {6, 7} — —
{4} {5} {5} {6, 7} — —
表2-6 例2.24的状态转换矩阵
I I+ I- Id I. Ie I I+ I- Id I. Ie
0 — — 1 — — 4 — — 4 — 3
1 — — 1 2 3 5 — — 6 — —
2 — — 4 — — 6 — — 6 — —
3 5 5 6 — —
2.3.4 DFA的化简
对于同一个正规语言可以由不同的有穷自动机所识别，识别同一个语言的多个自动机中，有的状态数目比较多，有的状态数目比较少，是否可以将状态数目比较多的自动机转化为等价的状态比较少的自动机呢？从理论上讲，每一个正规语言都可以由一个状态数最少的DFA所识别，而且这个DFA是唯一的。本节将介绍一种将DFA状态化简到最少的方法。首先介绍几个相关概念。
定义2.13（状态等价和状态可区别） 对于一个给定的DFA M = (Q，∑，δ，q0，F)，定义状态集Q上的等价关系如下：对于p，q∈Q，若对每个x∈∑*，δ(p，x) ∈F当且仅当δ(q，x)∈F，则称p和q等价，记作p≡q。否则，称p和q为可区别的。
上述定义的意思是说，从DFA M的两个状态p和q出发，在读过任何字符串x以后，它们或者都到达M的终态，或者都不到达M的终态，此时称p和q等价。需要注意的是，定义2.13并不要求对一切字符串x，都将p和q同时引向终态，或同时引向非终结状态。例如，对某个字符串x1，它将p和q同时引向终结状态，而对另一个字符串x2，它将p和q同时引向非终结状态，这是不违反p和q等价的要求的。相反的是，只要有一个字符串x，使得δ(p，x)在F中，而δ(q，x)不在F中，这就肯定p和q不等价了。从定义2.13也可明显看出，对任何一个DFA，其终态与非终态永远不会等价（也就是它们是可区别的）。例如，p∈F，q ? F，取ε∈∑*，则δ(p，ε)=p∈F，而δ(q，ε)=q ? F。所以p和q不等价。
对一个DFA M最少化的基本思想是把M的状态集划分为一些不相交的子集，使得任何两个不同子集的状态是可区别的，而同一子集的任何两个状态是等价的。最后，从每个子集选出一个代表，同时消去其他状态。下面是确定DFA状态集上所有状态对是否等价的极小化算法。
算法2.6 极小化算法
输入：一个DFA M=(Q, ∑, δ, q0, F)
输出：DFA M所有等价状态对
步骤：
1.为所有状态对(p，q) (p，q∈Q)画一张表，开始时表中每个格子内均为空白（未做任何标记）。
2.对p∈F，q ? F的一切状态对(p，q)，在相应的格子内做标记（例如画一个“×”）。
3.重复下述过程，直到表中内容不再改变为止：如果存在一个未被标记的状态对(p，q)，且对于某个a∈∑，(δ(p，a)，δ(q，a))已做了标记，则在(p，q) 相应的格子内做标记。
4.在完成步骤1、2、3之后，所有未被标记的状态对(p，q)都是等价的，即p≡q。
对上述算法有以下几点说明。在第2步，因为终态和非终态肯定是不等价的，所以对这些状态对首先做了标记。第3步是算法的主体，它由三重循环构成。中循环是扫描代表状态对的所有格子，如果存在一个尚未被标记的状态对(p，q)，则对于所有的a∈∑，检查(δ(p，a)，δ(q，a))是否已做了标记，如果已做了标记，则在(p，q) 相应的格子内做标记；否则，对下一个a再检查（这是内循环）。最外层循环是不断重复中循环的工作，直到表中内容不再改变为止。在这一过程中，对某些状态对(p，q)可能查看多次，因为这一轮扫描时未被标记，到下一轮扫描时就有可能被标记。
例2.25 对图2-16所对应的DFA用极小化算法进行化简。
解：在算法2.6的第1步中，对该DFA中的6个状态建立一个空白表，因为两状态等价是对称的，所以只用表的下三角部分即可，如表2-7所示。
在极小化算法的第2步之后，对终态和非终态的状态对的格子内做了标记，结果如表2-8所示。
在第3步，找出表2-8中尚未标记的状态对，例如(0，3)，对于a∈∑，有δ(0，a)=1，δ(3，a)=5，因为(1，5)未被标记，所以现在也不能标记(0，3)。 对于b∈∑，有δ(0，b)=2，δ(3，b)=5，因为(2，5)未被标记，所以现在仍不能标记(0，3)。由于∑中只有a、b两个符号，故(0，3)暂时无法标记。 基于同样的理由(0，4)和(1，2)也不能被标记。 但是对于(1，5)，对a∈∑，有δ(1，a)=3，δ(5，a)=5，而此时(3，5)已被标记，所以(1，5)也应被标记，对于b就不用再看了。类似地，可以标记(2，5)。接下来看(3，4)，对于a∈∑，有δ(3，a)=5，δ(4，a)=5，因为(5，5)等价，所以现在不能标记(3，4)。 对于b∈∑，也有同样情况，因此暂时无法标记(3，4)。至此，表中的情况如表2-9所示。
现在开始下一遍考察。对于(0，3)，仍与上次一样，有δ(0，a)=1，δ(3，a)=5。但此时(1，5)已于上一遍被标记，所以这一遍我们标记(0，3)。类似地，可以标记(0，4)。至于其他状态(1，2)和(3，4)，经考察仍不能做标记，这一遍结束。再做一遍仍然不能改变这一情况，所以算法结束。此时表中的情况如表2-10所示。
最后得出的结论是：1≡2和3≡4。
从集合{1，2}和{3，4}中分别选取一个代表，比如1和3。将原来指向2和4的有向边分别指向1和3，将原来以2和4为起点的有向边改为以1和3为起点，从而构造出具有4个状态的等价DFA，如图2-17所示。
可以证明从任何一个接受正规语言A且没有不可到达状态的DFA M出发，施用极小化算法，找出等价状态，然后通过合并等价状态所构造出的DFA，就是接受A的具有最小状态数的DFA。
图2-17 例2.25的已化简的DFA
