编译原理—清华大学—第2版—第4章词法必威体育精装版.ppt

NFA→DFA的过程(子集法): 假设NFA N=(K,∑,f,K0,Kt)按如下办法构造一个DFA M,使得L(M)=L(N). 不失一般性，设∑={a,b}，我们构造一张表: … 状态 =?-closure(move(Ti,a)) =?-closure(move(Ti,b)) T0= ?-closure( ) Ta Tb K0 首先，置第1行第1列为?-closure(K0)求出这一列的Ta，Tb； 然后，检查这两个Ta，Tb，看它们是否已在表中的第一列中出现，把未曾出现的填入后面的空行的第1列上，求出每行第2，3列上的集合... 重复上述过程，直到所有第2，3列子集全部出现在某行第一列为止。 … 状态 =?-closure(move(Ti,a)) =?-closure(move(Ti,b)) T0= ?-closure( ) Ta Tb K0 例 将下图的NFA N转换成DFA M 0 2 3 4 5 6 7 8 9 10 1 ε ε ε ε ε ε ε ε b b b a a NFA N 0 2 3 4 5 6 7 8 9 10 1 ε ε ε ε ε ε ε ε b b b a a 状态 T0= ?-closure({0}) ={0,1,2,4,7} {1,2,3,4,6,7,8}=T1 {1,2,4,5,6,7}=T2 T1= {1,2,3,4,6,7,8} T1 {1,2,4,5,6,7,9} =T3 T2= {1,2,4,5,6,7} T1 T2 T3= {1,2,4,5,6,7,9} T1 T4 T4= {1,2,4,5,7,10} T1 T2 =?-closure(move(Ti,a)) Ta =?-closure(move(Ti,b)) Tb 现在把这张表看成一个状态转换矩阵，把其中的每个子集看成一个状态。 这张表唯一刻划了一个确定的有限自动机M，它的初态是?-closure(K0) ，它的终态是含有原终态Kt的子集。 不难看出，这个DFA M与M’等价。 ?-closure(move(Ti,a)) ?-closure(move(Ti,b)) T0= ?-closure({0}) ={0,1,2,4,7} {1,2,3,4,6,7,8}=T1 {1,2,4,5,6,7} =T2 T1= {1,2,3,4,6,7,8} T1 {1,2,4,5,6,7,9} =T3 T2= {1,2,4,5,6,7} T1 T2 T3= {1,2,4,5,6,7,9} T1 T4 T4= {1,2,4,5,7,10} T1 T2 初态 终态 b 0 2 1 3 4 a b a a a a b b b DFA M 取Ti的下标i为状态名 四、DFA的最小化（化简） 最小状态DFA 没有多余状态(死状态) 没有两个状态是互相等价（不可区别） 多余状态：从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。 消除多余状态 s1 s5s2 s7s2 s5s5 s7s5 s6s3 s1s8 s0s0 s1s3 s6 0 1 011000110 s0s1s2s3s4s5s6s7s8 s1 s5s2 s7s2 s5s5 s7s3 s1s0 s1 0 1 011001 s0s1s2s3s5s7 两个状态s和t等价,满足: 一致性——同是终态或同是非终态 蔓延性——从s出发读入某个a(a∈∑)和从 t出发读入某个a到达的状态等价。 状态2和4是不等价的(可区别的)。 b 0 2 1 3 4 a b a a a a b b b DFA M 2是非终态而4是终态 状态2和3是不等价的，因为读入b后分别到达2和4，而2和4是不等价的。 对于一个DFA M =（K,∑,f,k0,kt)，存在一个最小状态DFA M’ =（K’,∑’,f’,k0’,kt’),使L(M’)=L(M). DFA的最小化算法的核心： 把一个DFA的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的. 将下图中的DFA M最小化 1,2,3,4,5,6,7 Ia: