第三章詞法分析(2)-免費(fèi)閱讀
【正文】 88 2. 反復(fù)應(yīng)用以下三條規(guī)則，消去 ?NFA M?中的狀態(tài)結(jié)點(diǎn)和弧，直至只剩下狀態(tài)結(jié)點(diǎn) X、 Y及連接二者 的弧。 p q w w or p q w w 76 DFA Minimization: Example f b c d e a g h g f e d c b 1. Initialize table entries: Unmarked, empty list A E B F C G D H 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 77 DFA Minimization: Example f b c d e a g h g f e d c b 2. Mark pairs of final amp。 ? 方法：劃分等價(jià)狀態(tài)集合 – Discover sets of equivalent states – Represent each such set with just one state 60 狀態(tài)等價(jià) ? Two states are equivalent if and only if: – The set of paths leading to them are equivalent – ????, transitions on ? lead to equivalent states (DFA) – ?transitions to distinct sets ? states must be in distinct sets 61 可區(qū)分狀態(tài) ? w( ? ?*)，區(qū)分狀態(tài) s和狀態(tài) t，如果： DFA M 從狀態(tài) s出發(fā)，經(jīng)過 w路徑到達(dá)某個接受狀態(tài)； 從 狀態(tài) t出發(fā)，經(jīng)過 w路徑到達(dá)某個非接受狀態(tài)；反之亦然。 方法：將 r分解成最基本的表達(dá)式， 使用下面的規(guī)則 1和規(guī)則 2為 r的每個基本符號構(gòu)造 NFA， 使用規(guī)則 3逐步組合前面構(gòu)造的 NFA直至得到完整的 NFA。 initialize ?closure(T) to T。 c ? nextchar。1 第 3章 詞法分析 ~ 有窮自動機(jī) 2 有 窮 自 動 機(jī) ? 語言的識別器是一個程序 ， 能判定字符串 x是否為該語言的句子 。 end。 while stack is not empty do begin pop the top element t off the stack。 43 首先構(gòu)造識別 ?和字母表中一個符號的 NFA ? 識別 {?}的 NFA i f start 對 ?， 構(gòu)造 NFA: i start a f 識別 {a}的 NFA 對 字母表中符號 a，構(gòu)造 NFA: 44 構(gòu)造識別主算符為選擇的正規(guī)式的 NFA 對于正規(guī)式 s | t ，構(gòu)造 NFA： ? f i start 識別 L(s )?L(t)的 NFA q1 N (s) N (t) ? ? ? q2 f1 f2 45 構(gòu)造識別主算符為連接的正規(guī)式的 NFA 對于正規(guī)式 st ，構(gòu)造 NFA： 識別 L(s)L(t) 的 NFA N(s) ? start q0 f0 N(t) ? ? i N(s) N(t) f start N(s)的接受狀態(tài)和N(t)的開始狀態(tài)合并 46 構(gòu)造識別主算符為閉包的正規(guī)式的 NFA 對于正規(guī)式 s* ，構(gòu)造 NFA： N(s) f start 識別正規(guī)式 (L(s))* 的 NFA i ? ? ? ? 47 ? 對于加括號的正規(guī)式 (s)，使用 N(s)本身作為它的 NFA。 ? 例如， ?區(qū)分任何接受狀態(tài)和非接受狀態(tài)； ? b區(qū)分狀態(tài) A和狀態(tài) B； ? b區(qū)分狀態(tài) B和狀態(tài) C； ? …… B D start a A a b b a b C b a 62 B start a A a b b a a E b D C b b a State A and state B are distinguished by the input bb. (a|b)*abb對應(yīng)的 DFA 63 DFA最小化算法 (Hopcroft算法 ) ? DFA最小化的方法是將 DFA的狀態(tài)劃分為不相交的組，同一個組中的狀態(tài)是不可區(qū)分的，不同組的狀態(tài)則可以由某個輸入串區(qū)分。 nonfinal states A E B F C G D H 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 78 f b c d e a g h g f e d c b DFA Minimization: Example 3. For each unmarked pair amp。在消去的過程中，用正規(guī)表達(dá)式標(biāo)記弧。 symbol, … A E B F C G D H 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 84 f b c d e a g h g f e d c b 4. Coalesce unmarked pairs of states. (a,e) a ? e b ? h d ? f A E B F C G D H 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 ae bh df c g 0 0 0 0 0 1 1 1 1 1 85 f b c d e a g h g f e d c b (a,e) None. A E B F C G D H 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 ae bh df c g 0 0 0 0 0 1 1 1 1 1 5. Delete unreachable states. 86 正規(guī)表達(dá)式和 NFA等價(jià) ? 任何一個正規(guī)表達(dá)式表示的語言，存在一個 NFA識別（ Thompson構(gòu)造法 ） ? 任何一個 NFA識別的語言，可以表示為一個正規(guī)表達(dá)式 – 拓廣狀態(tài)轉(zhuǎn)換圖的概念，轉(zhuǎn)移符號可以用一個正規(guī)表達(dá)式標(biāo)記 87 由帶 ?NFA 構(gòu)造正規(guī)表達(dá)式 方法： 1. 在 M的狀態(tài)轉(zhuǎn)換圖上增加狀態(tài) X, Y，從 X到初始狀態(tài) q0 用 ?弧連接，從 M的所有終態(tài)到 Y用 ?弧連接，得到的新的 NFA為 M?，它只有一個初始狀態(tài) X和一個終止?fàn)顟B(tài) Y。 ) b. Replace G in ?new by the set of all these subgroups. Minimizing the Number of States of DFA 66 3. Compare ?new and ?. I
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1