授课题目NFA确定化与DFA化简授课学时2授课时间2011.9教学重点、难点1. 带空边的非确定有限自动机确定化算法；2. 确定有限自动机化简算法；教学内容：1. 非确定有限自动机和确定有限自动机的等价性对任何一个NFA M，都存在一个DFA M’ , 使得L(M’)=L(M) 首先定义两个闭包：1) 设I是NFA M的状态集的子集，定义I的e闭包e_CLOSURE(I)为：a. 若q ∈I ,则q ∈e_CLOSURE(I)b. 若q ∈I,那么从q出发经任意条ε弧而能到达的任何状态q’都属于e_CLOSURE(I)2) 设I是NFA M 的状态集的子集，a∈∑,可以定义状态子集Ia∈S，对任一sj∈Ia，必有si∈I，使得si和sj之间存在一条由si指向sj的有向弧，弧上的标记字符恰为 aIa=e_CLOSURE(J) 其中，J是那些可从I中的某一状态节点出发经过一条a弧而能到达的状态节点的全体然后对给定的NFA按照如下的步骤进行确定化：(1) 构造一张表，共有|∑|+1列，第一列为状态子集I，然后对每个a∈∑分别设一列Ia；(2) 第一行第一列的状态子集为I为e_CLOSURE(s0),其中s0为初始状态；(3) 为第一列中的I和每个k∈∑求Ik，并记入相应的Ik列。
如果它和表格第一列中的所有状态子集均不相同，则此表生成一个新行，将它填入新行的第一列中4) 重复步骤（3），直到对每个I和k∈∑均已求得Ik，且不再生成新的状态子集为止此过程在有限步内一定可以终止，因为如果|S|=n，则状态子集最多只有2n 个，上述表最多只有2n行；(5) 将第一列中的每个状态子集重命名为新的状态，则上述表格便成为新的状态状换矩阵例 设有NFA M =({ 1 , 2, … 9} , { a , b } , f , {1}, {6 , 7 , 9 }), 其中f如图2.8所示.对此NFA ,我们首先构造一张表，表的每一行含有 |∑|+1 列将表的第二行的第一列处单元格的值置为ε__CLOSURE(s0)，这里为ε__CLOSURE(1)={1，2}然后我们开始计算表中其它单元格的值一般而言，如果某一行的第一列中的状态子集已经确定，记为I，那么对k∈∑求Ik，并记入这一行相应的Ik列然后我们检查这一行所有的状态子集Ik，看它们是否已经在表的第一列中出现过，如果某一个Ik没有出现过，则在此表的最下面生成一个新行，将它填入新行的第一列中 重复上述的过程，直至所有已生成的Ik 均已在表的第一列中出现过。
这种NFA确定化的方法称为子集法按照子集法NFA M进行确定化构造出的状态转换矩阵表如图所示 IIaIb{1,2}{2,4,5,6,7}{3,8}{2,4,5,6,7}φ{3,9,8}{3,8}{9}φ{3,9,8}{9}φ{9}φφ对NFA M进行确定化构造出的状态转换矩阵表对表格的状态子集进行重命名，分别用1、2、3、4、5来代表{1,2}、{2,4,5,6,7}、{3,8}、{3,9,8}、{9}这五个状态子集，形成如图2.10所示的状态转换矩阵，它即是和NFA M等价的DFA M’IAb123 2*435 4*5 5*和NFA M等价的DFA M’2. 确定有限自动机化简对同一个语言，可以有无限多个有限自动机来描述，从功能上看，这些有限自动机是等价的，但其构成的复杂程度差别很大；对一个NFA，把它确定化后，得到的DFA所具有的状态数可能并不是最小的那么，有没有一个最小的DFA呢，这就是有限自动机的化简或最小化问题一个确定有限自动机M的化简是指：寻找一个状态数最少的 DFA M’,使得L(M)=L(M’) 定义 设DFA M 的两个不同状态q1和q2 , 如果对任意输入的符号串x，从q1和q2出发，总是同时到达接受状态或拒绝状态中，则称q1和q2是等价的。
如果q1和q2不等价，则称q1和q2是可区分的显然，DFA的终止状态和非终止状态是不等价的定义 从有限自动机的初始状态开始，任何输入序列都不能到达的那些状态称为无关状态定义 如果DFA M 没有无关状态，也没有彼此等价的状态，则称DFA M 是最小的（或规约的）下面我们介绍一个常用的DFA化简方法：分离法，也称为划分法分离法的基本思想：首先DFA中的无关状态，可以直接去掉，对DFA的功能无影响然后将DFA的状态集划分为一些不相交的子集，使得任何两个不同子集中的状态都是可区分的，而同一子集中的任何两个状态都是等价的，然后在每一个子集中选一个代表，合并掉其它的等价状态，这样就得到了一个最小的DFA分离法的步骤：首先，把状态集中的终止状态和非终止状态分开，生成两个状态子集，形成初始划分I ,显然分别属于这两个集合的状态是可区分的假定分离进行到某个时刻I中包含m个子集，记作 I={I1,I2,…Im}其中，属于不同子集的状态是可区分的检查 I中的每个子集Ii看能否进一步划分对于某个Ii，令Ii={q1,q2,…qk},若存在一个输入字符a使得Ii中的各状态遇到输入a后转移的后继状态不全在某一现存的子集中，则对Ii进行进一步的划分。
例如，假定状态q1,q2经a弧分别到达状态t1和t2,而t1和t2属于现行划分中的两个不同子集，则将Ii分裂成两个新的集合，使得一半含有q1,另一半含有q2，形成新的划分一般地，若Ii经过a弧落入现行划分中的N个不同子集，则应将Ii划分为N个不相交的组，使得同一个组中的所有状态经a弧都落入当前划分的同一个子集中，这样形成新的划分重复上述过程，直至划分中所含的子集数不再增长为止至此，每个子集已不可再分，也就是说，每个子集中的状态是相互等价的，而不同子集中的状态是可区分的 经上述过程后，我们得到了一个最后划分，对这个划分中的每个子集，我们选取子集中的一个状态来代表例如，对于子集Ii={q1,q2,..qn}, 我们可选择其中的任意一个，比如q1,来代表这个子集在原来的自动机中，凡是射入到q2,q3,qn的有向弧都改成射入到q1 所有这些选出的状态组成了新的最简自动机的状态集S’而且，若Ii中含有原自动机的初始状态，则选出的代表状态q1即为新的最简自动机的初始状态；若Ii中含有原自动机的终止状态，则选出的代表状态q1即为新的最简自动机的终止状态例：2.12 对图2.11所示的DFA M进行最小化。
图 2.11 DFA M首先，把DFA M的状态集划分为两个子集：终态子集{E}和非终态子集{A,B,C,D}然后，对每一个子集考察其是否需要进一步划分对终态子集{E}，因为其中只有一个状态，所以无需进一步划分对非终态子集{A,B,C,D}，有可能需要进一步划分遇到输入符号a时，状态A,B,C,D转换的后继状态都在子集{A,B,C,D}中，转移的行为一致，所以对符号a而言，子集{A,B,C,D}不需要进一步划分；遇到输入符号b时，状态A,B,C都转换到子集{A,B,C,D}中，而状态D转换的后继状态在子集{E}中，转移的行为不一致，因此，所以对符号b而言，子集{A,B,C,D}需要进一步划分因此，根据转移行为的相同与否，将子集{A,B,C,D}划分为两个新的子集，即{A,B,C}和{D}这时，原DFA M的状态集被划分为三个状态子集{A,B,C}、{D}和{E}显然，状态子集{D}和{E}中都只有一个状态，不可能进一步划分继续考察状态子集{A,B,C}遇到输入符号a时，状态A,B,C转换的后继状态都在子集{A,B,C}中，转移的行为一致，所以对符号a而言，子集{A,B,C}不需要进一步划分；遇到输入符号b时，状态A、C转移的后继状态在子集{A,B,C}中，状态B转移的后继状态在子集{D}中，因此，对符号b而言，子集{A,B,C}需要进一步划分。
将子集{A,B,C}划分为两个新的子集{A,C}和{B}这时，原DFA M的状态集被划分为四个状态子集{A,C}、{B}、{D}和{E}再考察子集{A,C}，对输入符号a,状态A、C都转移到状态B∈{B}；对输入符号b,状态A、C都转移到状态C∈{A,C},所以无需进一步划分至此，原DFA M的状态集最终被划分为四个状态子集{A,C}、{B}、{D}和{E}最后，我们从每个状态子集中选一个状态来代表这个状态子集，这些选出的状态组成了新的最简DFA M’的状态集，含有原DFA M的初始状态的状态子集成为最简DFA M’的初始状态，含有原DFA M的终止状态的状态子集成为最简DFA M’的终止状态这里，我们随意选取A、B、D、E这四个状态来分别代表四个状态子集{A,C}、{B}、{D}和{E}，则最简DFA M’的状态集为{A,B,D,E}，初始状态为A,终止状态为E,如图2.12所示 图2.12 简化后的DFA M’。