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