[理學(xué)]編譯原理 第三章(文件)
【正文】 switch(state) { case 1: switch(ch){ case a: state=1。 default: state=0。break。break。 case b:state=0。} break。 ch==eof) return (1)。然后在自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換表中尋找相同的兩行，如這兩行對(duì)應(yīng)的狀態(tài) S i和 Sj屬于同一類，則可以合并。 分離法算法 開始時(shí)將自動(dòng)機(jī)的狀態(tài)分成兩類：所有接受狀態(tài)為一類，所有非接受狀態(tài)為一類。 按步驟 2得到最終的類劃分后，取每一類中的一個(gè)狀態(tài)作代表，而刪除其他一切等價(jià)的狀態(tài)，則所有這些狀態(tài)代表構(gòu)成了最小化自動(dòng)機(jī) M’的狀態(tài)集合。 轉(zhuǎn)換規(guī)則 RE=? ? RE=a a RE=AB SFA(A) SFA(B) ? RE=A|B SFA(A) SFA(B) ? ? ? ? RE=A* SFA(A) ? ? ? ? 練習(xí)： (a|b)*(aa|bb)(a|b)* （ a*|b*） b(ba)* 為正則表達(dá)式 (a|b)*a(a|b)構(gòu)造一個(gè) DFA。 例、將以下自動(dòng)機(jī)最小化： A B F C D E G a b a b b b b a b a 例： P98（例 ） 六、正則表達(dá)式到 DFA的轉(zhuǎn)換 正則定理 ：對(duì)于任意的正則表達(dá)式 RE，均可構(gòu)造一個(gè)有 窮自動(dòng)機(jī) FA，使得 FA所接受的符號(hào)串的集合 與 RE所接受的符號(hào)串集合等價(jià)。如果兩個(gè)狀態(tài) P和 Q屬于同一類，當(dāng)且僅當(dāng)對(duì)于任何輸入字符 a，狀態(tài) P和 Q轉(zhuǎn)換成的狀態(tài)均屬于已有的同一類。 分離法 對(duì)自動(dòng)機(jī) M進(jìn)行最小化，即尋找一個(gè)狀態(tài)數(shù)比 M更少的DFA M’，使得 M和 M’所識(shí)別的符號(hào)串相同。 } ? 合并 : ?closure(SS) 計(jì)算 ?closure(SS)算法 (見(jiàn) P95)： 【 1】 首先令 ?closure(SS) 包含 SS； 【 2】 若 S? ?closure(SS) ，且 S S1,S1? ?closure(SS), 則將 S1加入到 ?closure(SS)中； 【 3】 直到 ?closure(SS)中沒(méi)有一個(gè)狀態(tài) S有 ?邊指向 ?closure(SS) 以外的狀態(tài)為止。 } if (state==3 amp。 default: state=0。 a b 10 1 2 2 3 2 3* 3 0 初始狀態(tài)為： 1 終止?fàn)顟B(tài)為： 3 無(wú)效狀態(tài)為： 0 case 3: switch(ch){ case a:state=3。break。} b
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1