【正文】 國防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 逐步把這個(gè)圖轉(zhuǎn)變?yōu)槊織l弧只標(biāo)記為 ?上的一個(gè)字符或 ?，最后得到一個(gè) NFA M?，顯然L(M?)=L(V) 國防科技大學(xué)計(jì)算機(jī)系 602教研室 ? (a|b)*(aa|bb)(a|b)* X Y (a|b)*(aa|bb)(a|b)* X Y ? 5 1 4 2 3 6 a b ? ? ? a b a b a b 國防科技大學(xué)計(jì)算機(jī)系 602教研室 I Ia Ib {X,5,1} {5,3,1} {5,4,1} {5,3,1} {5,2,3,1,6,Y} {5,4,1} {5,4,1} {5,3,1} {5,2,4,1,6,Y} {5,2,3,1,6,Y} {5,2,3,1,6,Y} {5,4,6,1,Y} {5,4,6,1,Y} {5,3,6,1,Y} {5,2,4,1,6,Y} {5,2,4,1,6,Y} {5,3,6,1,Y} {5,2,4,1,6,Y} {5,3,6,1,Y} {5,2,3,1,6,Y} {5,4,6,1,Y} X Y ? 5 1 4 2 3 6 a b ? ? ? a b a b a b 國防科技大學(xué)計(jì)算機(jī)系 602教研室 I a b 0 1 2 1 3 2 2 1 4 3 3 4 4 6 5 5 6 5 6 3 4 0 1 2 3 5 4 6 a a b b b a b a a b a b a b 國防科技大學(xué)計(jì)算機(jī)系 602教研室 確定有限自動(dòng)機(jī)的化簡 ? 對 DFA M的化簡 :尋找一個(gè)狀態(tài)數(shù)比 M少的 DFA M?，使得 L(M)=L(M?) ? 假設(shè) s和 t為 M的兩個(gè)狀態(tài)，稱 s和 t等價(jià) :如果從狀態(tài) s出發(fā)能讀出某個(gè)字 ?而停止于終態(tài)，那么同樣，從 t出發(fā)也能讀出 ?而停止于終態(tài)；反之亦然。 ? 兩個(gè)狀態(tài)不等價(jià)，則稱它們是 可區(qū)別 的。 國防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 對一個(gè) DFA M最少化的基本思想 : 把 M的狀態(tài)集劃分為一些不相交的子集，使得任何兩個(gè)不同子集的狀態(tài)是可區(qū)別的，而同一子集的任何兩個(gè)狀態(tài)是等價(jià)的。最后，讓每個(gè)子集選出一個(gè)代表，同時(shí)消去其他狀態(tài)。 國防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 具體做法 : 對 M的狀態(tài)集進(jìn)行劃分 ?首先，把 S劃分為終態(tài)和非終態(tài)兩個(gè)子集，形成基本劃分 ?。 ?假定到某個(gè)時(shí)候， ?已含 m個(gè)子集，記為?={I(1)， I(2)， ? ， I(m)}，檢查 ?中的每個(gè)子集看是否能進(jìn)一步劃分 : ?對某個(gè) I(i)，令 I(i)={s1,s2, ? ,sk}，若存在一個(gè)輸入字符 a使得 Ia(i) 不會包含在現(xiàn)行 ?的某個(gè)子集 I(j)中，則至少應(yīng)把 I(i)分為兩個(gè)部分。 國防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 例如，假定狀態(tài) s1和 s2經(jīng) a弧分別到達(dá) t1和t2，而 t1和 t2屬于現(xiàn)行 ?中的兩個(gè)不同子集，說明有一個(gè)字 ?， t1讀出 ?后到達(dá)終態(tài)，而t2讀出 ?后不能到達(dá)終態(tài)，或者反之，那么對于字 a? ， s1讀出 a?后到達(dá)終態(tài)，而s2讀出 a?不能到達(dá)終態(tài)，或者反之，所以s1和 s2不等價(jià)。則將分成兩半，使得一半含有 s1: I(i1)={s|s?I(i)且 s經(jīng) a弧到達(dá) t, 且 t與 t1屬于現(xiàn)行 ?中的同一子集 } 另一半含有 s2: I(i2)=I(i)I(i1) 國防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 一般地，對某個(gè) a和 I(i)，若 Ia(i) 落入現(xiàn)行 ?中 N個(gè)不同子集，則應(yīng)把 I(i)劃分成 N個(gè)不相交的組，使得每個(gè)組 J的 Ja都落入的 ?同一子集。這樣構(gòu)成新的劃分。 ? 重復(fù)上述過程，直到 ?所含子集數(shù)不再增長。 ? 對于上述最后劃分 ?中的每個(gè)子集，我們選取每個(gè)子集 I中的一個(gè)狀態(tài)代表其他狀態(tài)，則可得到化簡后的 DFA M?。 ? 若 I含有原來的初態(tài)，則其代表為新的初態(tài)，若 I含有原來的終態(tài)，則其代表為新的終態(tài) 。 國防科技大學(xué)計(jì)算機(jī)系 602教研室 0 1 2 3 5 4 6 a a b b b a b a a b a b a b I(1)={0, 1, 2} I(2)={3, 4, 5, 6} Ia(1) ={1, 3} I(11) ={0, 2} I(12) ={1} I(2)={3, 4, 5, 6} I(11) ={0, 2} Ia(11) ={1} Ib(11) ={2, 5} I(111) ={0} I(112) ={2} I(12) ={1} I(2)={3, 4, 5, 6} Ia(2) ={3, 6} Ia(2) ={4, 5} 國防科技大學(xué)計(jì)算機(jī)系 602教研室 0 1 2 3 5 4 6 a a b b b a b a a b a b a b 0 1 2 3 a a b b b a a b 國防科技大學(xué)計(jì)算機(jī)系 602教研室 詞法分析器的自動(dòng)產(chǎn)生 LEX 詞法分析程序自動(dòng)產(chǎn)生器 詞法分析程序 L LEX源程序 詞法分析程序 L 單詞符號 輸入串 狀態(tài)轉(zhuǎn)換矩陣 控制執(zhí)行程序 國防科技大學(xué)計(jì)算機(jī)系 602教研室 AUXILIARY DEFINITION letter?A|B|...|Z digit ?0|1|...|9 RECOGNITION RULES 1 DIM { RETURN (1,) } 2 IF { RETURN (2,) } 3 DO { RETURN (3,) } 4 STOP { RETURN (4,) } 5 END { RETURN (5,) } 6 letter(letter|digit) * { RETURN (6, TOKEN) } 7 digit(digit)* { RETURN (7, DTB) } 8 = { RETURN (8, ) } 9 + { RETURN (9,) } 10 * { RETURN (10,) } 11 ** { RETURN (11,) } 12 , { RETURN (12,) } 13 ( { RETURN (13,) } 14 ) { RETURN (14,) } 國防科技大學(xué)計(jì)算機(jī)系 602教研室 ? LEX的工作過程： ?首先，對每條識別規(guī)則 Pi構(gòu)造一個(gè)相應(yīng)的非確定有限自動(dòng)機(jī) Mi； ?然后，引進(jìn)一個(gè)新初態(tài) X，通過 ?弧，將這些自動(dòng)機(jī)連接成一個(gè)新的 NFA； ?最后，把 M確定化、最小化，生成該 DFA的狀態(tài)轉(zhuǎn)換表和控制執(zhí)行程序 國防科技大學(xué)計(jì)算機(jī)系 602教研室 X ? P2 ? ? ? M1 Mm M2 P1 Pm ? ? 國防科技大學(xué)計(jì)算機(jī)系 602教研室 作業(yè) ? P647， 8， 12， 14 國防科技大學(xué)計(jì)算機(jī)系 602教研室 例 : 對下圖 NFA M構(gòu)造其 DFA. a a b b b X Y 解 : 用子集法構(gòu)造轉(zhuǎn)換矩陣 I I a I b{ x } { x , y } { y }{ y } { x , y }{ x , y } { x , y } { x , y } 字符狀態(tài)a b0 2 11 22 2 2不可識別 ba ! 國防科技大學(xué)計(jì)算機(jī)系 602教研室 {1, 2} {0} a b a,b a b 0 2 1 DFA M’ a a,b a b 0 1 化簡后的 DFA M’ ba ?。?！