编译原理第三章必威体育精装版.ppt

TJNU-COCIE-WJW * * [例如，假定状态s1和s2经a弧分别到达状态t1和t2，而t1和t2属于现行П的两个不同的子集，那就将I(i)分成两半I(i1)和I(i2) 使得一半含有s1： I(i1)={s|s∈ I(i)且s经a弧到达t1所在的子集中的某状态} 另一半含有s2： I(i2)= I(i) - I(i1) ] 注意：由于t1和t2是可区别的，即存在一个字w，t1将读出w而停于终态，而t2或读不出w或虽然可读出w但不到达终态；或者情形恰好相反。因而字aw就将状态s1和s2区别开来。也就是说I(i1)中的状态与I(i2)中的状态是可区别的 ③一般地，若I(i)a落入现行П中N个不同子集，则应将I(i)划分为N个不相交的组，使得每个组J的Ja都落入П的同一子集，这样再形成新的分划 TJNU-COCIE-WJW * * ④重复上述过程，直至分划中所含的子集数不再增长为止。至此，П中的每个子集已不可再分。也就是说，每个子集中的状态是互相等价的，而不同子集中的状态则是互相可区别的。 ⑤经过上述过程后，得到一个最后分划П.对于这个П中的每个子集，选取子集中的一个状态代表其它状态。 [例如，假定I={q1 ,q2 ,…,qk}是这样一个子集，可挑选q1代表这个子集。在原来的自动机中，做： a.凡导入到q2 ,…,qk的弧都改成导入q1 b.将q2 ,…,qk从原来的状态集S中删除 c.若I中含有原来的初态，则q1是新初态 d.若I中含有原来的终态，则q1是新终态] 到此，得到一个化简得DFA M’，使得 L( M )=L( M’) TJNU-COCIE-WJW * * 6. 例题 例1:把DFA M’进行化简 例2：设计一个DFA，其输入字母表是{a，b}，它能接受以a开始以b结尾的所有序列。 TJNU-COCIE-WJW * * 例1:把DFA M’进行化简 解: ①把M状态集分为两组: 终态结点{3，4，5，6} 非终态结点{0，1，2} ②考察{3，4，5，6} 因为， {3，4，5，6}a = {3，4，5，6}b = 所以， {3，4，5，6}不可再分 ③考察{0，1，2} 因为， {0，1，2}a = 所以， {0，1，2}必可再分 看图，把{0，1，2}分割为{1}和{0，2} {3，6} {4，5} {3，4，5，6} {3，4，5，6} J={3，6} J={4，5} {1，3} {3，4，5，6} J={1，3} {0，1，2} TJNU-COCIE-WJW * * ④考察{0，2} 因为， {0，2}a = {0，2}b = 所以， {0，2}必可再分 所以，把M分割为{0}， {1}，{2}，{3，4，5，6} ⑤用状态3代替状态4，5，6，把引向状态4，5，6的箭弧都引向状态3，把4，5，6消去，得到一个DFA M’ J={1} J={2，5} {1} {1} {2，5} {3，4，5，6} {0，2} {1} TJNU-COCIE-WJW * * TJNU-COCIE-WJW * * 例2：设计一个DFA，其输入字母表是{a，b}，它能接受以a开始以b结尾的所有序列。 解: (1)根据题意，得到相应的正规式： a(a|b)*b (2)由以上正规式构造相应的NFA为： TJNU-COCIE-WJW * * ① ② a(a|b)*b TJNU-COCIE-WJW * * ③ TJNU-COCIE-WJW * * ④ 得到一个NFA M’ 且 L(M’) = L(V) TJNU-COCIE-WJW * * (3)用子集法对M’进行确定化 ①构造一张表 I Ia =ε_CLOSURE(J) Ib =ε_CLOSURE(J) J={1} -- {X} {1, 2, 3} {1, 2, 3} {2, 3} {2, 3} {2, 3, Y} -- {2, 3} {2, 3, Y} {2, 3} {2, 3, Y} {2, 3, Y} J={2} J={2, Y} J={2} J={2, Y} J={2} J={2, Y} TJNU-COCIE-WJW * * I Ia =ε_CLOSURE(J) Ib =ε_CLOSURE(J) {X} {1, 2, 3} {2, 3} {2, 3, Y} {1, 2, 3} {2, 3} {2, 3} {2, 3} -- {2, 3, Y} {2, 3, Y} {2, 3, Y} ②把每个子集看成一个状态，得到一个DFA M， 且L(M) = L(M’) s a b 0 1 2 3 1 2 2 2 -- 3 3 3 0 1 2