1、第六讲 正规式与有限自动机的等价7 正规式与有限自动机等价A. 上的 NFA M能识别的字的全体 L(M)是 上的正规式B. 对 上任何正规式 V,存在一个 上的确定的有限自动 机 M,使得 L(V) = L(M)证 A. 将 NFA M化为正规式要点 : (I) 引入两个结点 X, Y; 按以下方式得等价的 M用 弧连接 X及 M的所有初态 ;用 弧连接 Y及 M的所有终态(II) 消去 M中所有结点直至剩下 X和 Y为止 .转换法则（ P54图 3.10 ） V1 V2V1 V2 V2 V1 V3V1 V2 V1|V2 V1（ V2） * V3 证 B. 就正规式 V,引入初态 X和终态
2、Y.先构造 NFAV 法则 (P50图 3.7): 确定化 : 给定 I为 M的状态子集 , a为 中字符 . 引入概念 I的 闭包 ,记为 _closure(I): (a) I中元在闭包中 (b)一切 I中元通过 弧能到的状态Ia= _closure(J): J是所有那些由 I中元经 a弧能到达的状态全体X Y例子I= _closure(1) = 1,2 Ia = _closure(J)= _closure(3,4,5) = 2,3,4,5,6,7,8a a a15263 84 7转换矩阵构造过程 (确定化 )设 =a, b, NFA M 初态集为 XI Ia Ib_closure(X) 依
3、 Ia 计算 依 Ib 计算选取未出现在第一列者填入第一列下行 位置作为 I, 重新计算 Ia 和 Ib 例 : 为正规式 (a|b)* (aa|bb)(a|b)*设计 DFA(1) 对应的 NFA (a|b)* (aa|bb)(a|b)*a a a a b b b b X YX 5 1342 6 Y构造转换矩阵进行确定化 (P50表 3.3)I Ia IbX,5,1 5,3,1 5,4,15,3,1 5,1,3,2,6,Y 5,1,4最后对表项进行编号 ,以新编号重新绘图 .含原初态的编号为初态 ,含原终态的编号为终态 . (参见P51图 3.8)8 DFA 的化简A. 等价DFA M中两个
4、状态 s, t 等价 , 如果 L(s)=L(t). (即从 s出发识别的字集等于从 t出发读出的字集 )B. 可区分L(s) L(t). 如终态 - 可读 非终态 - 不识别 所以二者不等价例 P51的图 3.8中状态 1 和 2可以区分C. DFA M状态最少化算法原理把 M的状态集分为一些不相交的子集 ,使得任何两个不同的子集的状态是可分的 ; 同一子集中的任何两个状态都是等价的.最后从每个子集选出一个代表 ,同时消区其它等价状态 .D. 最少化算法 (P56-58) 例子 3.6 (P51图 3.8)I) 令 = S1, S2S1为非终态集 ; S2为终态集 . 可区分II) 设 =
5、S1, S2, , Sn (Si , Sj 可区分 , 各 Si 待 区分 )如果存在 a和某个 Si , 使得 Sia 分别落在 中 p 个不同的子集 , 则将 Si 分为 p 个 更小的状态子集 Si1, Si2, , S ip, 使得对每个 Sij 而言 , Sija全部包含在 中的同一子集中 . (注意 : Si 中 一切遇 a 无定义的状态归为一类 (一个子集 ) 如此 , 每细分一次得一个 newIII) 若 new , 则将 new 作为 重复 II)IV) 对 中任意子集 Si = Si1, Si2, , Sik选一个代表状态如 Si1. 将 原来导入Si2, , Sik的弧 改为导入 Si1. 然后删除 Si2, , Sik. Si1为新的初态 Si 中有原 初态 ; Si1为新的终态 Si 中有原终态V) 在 IV步结果基础上 ,删除所有无用状态 . 即从初态永远到达不了的那些状态 .作业P64:7(1)14
