從正規(guī)式到詞法分析(編輯修改稿)
2025-09-11 20:25 本頁面
【文章內(nèi)容簡介】 ，效率低 。 改進(jìn)方法： 將 NFA上的全部路徑均確定化并且記錄下來，得到與NFA等價(jià)的 DFA。 甲乙123ccccbb甲 1,2 3, 乙3 乙cbcbb 回顧從甲地到乙地的路徑，它的數(shù)學(xué)模型實(shí)質(zhì)上是一個(gè) NFA （右上） 。 可以找到一個(gè)等價(jià)的 DFA（右下），它們識別的路徑均是： cc ccb cbb 例 用 DFA識別 cc和 cbc： 甲 c {1,2} c {3,乙 }， 接受 甲 c {1,2} b {3} c ?， 不接受 優(yōu)點(diǎn)： 1. 消除了不確定性（將 NFA的下一狀態(tài)集合并為一個(gè)狀態(tài)） 2. 無需動態(tài)計(jì)算狀態(tài)集合（針對模擬 NFA的算法） 10 算法 從 NFA構(gòu)造 DFA（子集法） NFA到 DFA（續(xù) 5） 輸入 NFA N 輸出 等價(jià)的 DFA D。 初態(tài)含有 NFA初態(tài) ， 終態(tài)集是含有 NFA終態(tài)的狀態(tài)集合 方法 用下述過程構(gòu)造 DFA ： ε 閉包 ({s0})是 Dstates僅有的狀態(tài) ， 且尚未標(biāo)記 。 while Dstates有尚未標(biāo)記的狀態(tài) T loop 標(biāo)記 T。 for 每一個(gè)輸入字符 a loop U := ε 閉包 (smove(T， a))。 if U不在 Dstates中 then U作為尚未標(biāo)記的狀態(tài)加入 Dstates。 end if。 Dtran[T， a] := U。 記錄狀態(tài)轉(zhuǎn)移 end loop。 end loop。 ■ 與 算法 ： 記錄了 所有 狀態(tài) 與 狀態(tài)轉(zhuǎn)移 兩個(gè)數(shù)據(jù)結(jié)構(gòu) ： Dstates(狀態(tài) )， Dtran(狀態(tài)轉(zhuǎn)移 ) 11 NFA到 DFA（續(xù) 6） 例 用算法 (a|b)*abb的 DFA 0 10124356 7 8 9abεε εεεεεε a b bε 閉包 ({0})={0,1,2,4,7}* A ε 閉包 (smove(A, a))={3,8,6,7,1,2,4}* B ε 閉包 (smove(A, b))={5,6,7,1,2,4}* C ε 閉包 (smove(B, a))={3,8,6,7,1,2,4} B ε 閉包 (smove(B, b))={5,9,6,7,1,2,4}* D ε 閉包 (smove(C, a))={3,8,6,7,1,2,4} B ε 閉包 (smove(C, b))={5,6,7,1,2,4} C ε 閉包 (smove(D, a))={3,8,6,7,1,2,4} B ε 閉包 (smove(D, b))={5,10,6,7,1,2,4}* E ε 閉包 (smove(E, a))={3,8,6,7,1,2,4} B ε 閉包 (smove(E, b))={5,6,7,1,2,4} C 1032aabbbbaa問題： 用哪個(gè)DFA識別輸入序列？ 識別 abb和 abab： A a B b D b E 接受 A a B b D a B b D 不接受 ABabCaDbabaEbab12 最小化 DFA 定義 對于任何兩個(gè)狀態(tài) t和 s，若從一狀態(tài)出發(fā)接受輸入字符串ω ，而從另一狀態(tài)出發(fā)不接受 ω ，或者從 t出發(fā)和從 s出發(fā)到達(dá)不同的接受狀態(tài)，則稱 ω 對狀態(tài) t和 s是 可區(qū)分 的。 ■ 反方向思考定義 ： 設(shè)想任何輸入序列 ω 對 s和 t均是不可區(qū)分的，則說明從 s出發(fā)和從 t出發(fā)，分析任何輸入序列 ω 均得到相同結(jié)果。 因此， s和 t可以合并成一個(gè)狀態(tài)。 引入一個(gè)“可區(qū)分”的概念： 正規(guī)式－ NFA－ DFA 13 算法 最小化 DFA的狀態(tài)數(shù) 最小化 DFA（續(xù) 1） 輸入 DFA D={S， ∑ ， move， s0， F}。 輸出 等價(jià)的 D?={S?， ∑ ， move?， s0?， F?}， （ D?狀態(tài)
高考資料相關(guān)推薦
鄂ICP備17016276號-1