[理學]編譯原理第三章(已改無錯字)
2022-11-16 21:34:15 本頁面
【正文】 case b: state=2。break。 default: state=0。break。} break。 a b 10 1 2 2 3 2 3* 3 0 初始狀態(tài)為： 1 終止狀態(tài)為： 3 無效狀態(tài)為： 0 case 3: switch(ch){ case a:state=3。break。 case b:state=0。break。 default: state=0。break。} break。 getch( )。 } if (state==3 amp。amp。 ch==eof) return (1)。 return(0)。 } ? 合并 : ?closure(SS) 計算 ?closure(SS)算法 (見 P95)： 【 1】 首先令 ?closure(SS) 包含 SS； 【 2】 若 S? ?closure(SS) ，且 S S1,S1? ?closure(SS), 則將 S1加入到 ?closure(SS)中； 【 3】 直到 ?closure(SS)中沒有一個狀態(tài) S有 ?邊指向 ?closure(SS) 以外的狀態(tài)為止。 ? 四、 NFA到 DFA的轉(zhuǎn)換過程 1 2 3 4 5 6 7 ? ? ? ? ? ? x z y ?closure({1})={1,2,3,4} ?closure({2})={1,2,3,4} ?closure({3})={1,2,3,4} ?closure({4})={1,2,3,4} ?closure({5})={5,6,7} ?closure({6})={6,7} NFA轉(zhuǎn)換成 DFA （ 1）不含 ?邊的 NFA轉(zhuǎn)換 DFA：圖 321轉(zhuǎn)換成圖 325 （ 2）包含 ?邊的 NFA轉(zhuǎn)換 DFA：圖 331轉(zhuǎn)換成圖 333 （ 3） NFA轉(zhuǎn)換成 DFA的算法： P95圖 329 五、確定有限自動機的最小化 * 合并法 首先將自動機的狀態(tài)分成兩類：所有接受狀態(tài)為一類，所有非接受狀態(tài)為一類。然后在自動機的狀態(tài)轉(zhuǎn)換表中尋找相同的兩行，如這兩行對應的狀態(tài) S i和 Sj屬于同一類，則可以合并。用 ?（ Si,Sj）表示 Si吸收 Sj，則 .若 Sj是開始狀態(tài)，則 Si成為開始狀態(tài)； .刪除狀態(tài)轉(zhuǎn)換表中的 Sj行； .將狀態(tài)轉(zhuǎn)換表中的 Sj統(tǒng)統(tǒng)改為 Si。 分離法 對自動機 M進行最小化，即尋找一個狀態(tài)數(shù)比 M更少的DFA M’，使得 M和 M’所識別的符號串相同。 自動機最小化的關(guān)鍵在于把它的狀態(tài)集分成一些兩兩互不相交的子集，使得任何兩個不同子集中的狀態(tài)都是不等價的，而同一子集中的所有狀態(tài)都是等價的，這樣以一個狀態(tài)為代表而刪除其它等價的狀態(tài)，也就獲得了狀態(tài)個數(shù)最少的 DFA。
教學課件相關(guān)推薦
鄂ICP備17016276號-1