[理學(xué)]編譯原理第三章-wenkub.com
2024-10-13 21:34 本頁(yè)面
【正文】 結(jié)構(gòu)化自動(dòng)機(jī)（ SFA）的特點(diǎn)： （ 1） SFA只有一個(gè)入口狀態(tài)和一個(gè)出口狀態(tài)； （ 2） SFA的入口狀態(tài)和出口狀態(tài)不重疊； （ 3） SFA的入口狀態(tài)沒(méi)有輸入邊，出口狀態(tài)沒(méi)有輸出邊； （ 4） SFA的其他狀態(tài)無(wú)指向 SFA外部的邊，也無(wú)從 SFA外部指 向 SFA內(nèi)部的邊。如發(fā)現(xiàn)某一狀態(tài)集中有不等價(jià)的狀態(tài)，則應(yīng)將它們分離，重復(fù)以上過(guò)程，直到不再產(chǎn)生新的類為止。 自動(dòng)機(jī)最小化的關(guān)鍵在于把它的狀態(tài)集分成一些兩兩互不相交的子集，使得任何兩個(gè)不同子集中的狀態(tài)都是不等價(jià)的，而同一子集中的所有狀態(tài)都是等價(jià)的，這樣以一個(gè)狀態(tài)為代表而刪除其它等價(jià)的狀態(tài)，也就獲得了狀態(tài)個(gè)數(shù)最少的 DFA。 ? 四、 NFA到 DFA的轉(zhuǎn)換過(guò)程 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 五、確定有限自動(dòng)機(jī)的最小化 * 合并法 首先將自動(dòng)機(jī)的狀態(tài)分成兩類：所有接受狀態(tài)為一類，所有非接受狀態(tài)為一類。amp。break。break。 default: state=0。 case 2: switch(ch) { case a: state=3。break。amp。 else return(0)。 ch=input[in++]。 ch=input[in++]。 稱字符串 a1,a2,…an 被有窮自動(dòng)機(jī)所接受，如果存在 狀態(tài)序列 S0， S1， …Sn, 使得 S0 S1, S1 S2, …, Sn 1 Sn 其中 S0為初始狀態(tài)， Sn為一個(gè)終止?fàn)顟B(tài)，中間狀態(tài)可以為初始狀態(tài)，也可為一個(gè)終止?fàn)顟B(tài)。 由于正則定義可以引入變量，因此正則定義比正則表達(dá)式的表達(dá)能力強(qiáng)。 ? 是正則表達(dá)式 , L( ? )={ } ? 是正則表達(dá)式 , L(? ) = {? } a ? ? 是正則表達(dá)式 , L( a )= { a } 例、以 00結(jié)尾的二進(jìn)制數(shù)字串對(duì)應(yīng)的正則表達(dá)式為： 設(shè) A,B? , 則 : R ? (A) ? R? , L((A) )=L(A)。 修正的方法 ? 從剩余的輸入中刪除一個(gè)字符； ? 向剩余的輸入中插入一個(gè)遺漏的字符； ? 用一個(gè)字符替換另一個(gè)字符； ? 交換兩個(gè)相鄰字符；
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1