第三章詞法分析(2)-資料下載頁(yè)
2025-07-22 09:42本頁(yè)面
【正文】 rked pair amp。 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 h ?? b f ?? f Maybe. Yes. 81 f b c d e a g h g f e d c b (a,e) (g,a) (g,a) 3. For each unmarked pair amp。 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 82 f b c d e a g h g f e d c b a e b f c g d h 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 (a,e) (g,a) (g,a) Need to mark. So, mark (g,a) also. 3. For each unmarked pair amp。 symbol, … 83 f b c d e a g h g f e d c b (g,a) (a,e) 3. For each unmarked pair amp。 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à) ? 任何一個(gè)正規(guī)表達(dá)式表示的語(yǔ)言，存在一個(gè) NFA識(shí)別（ Thompson構(gòu)造法 ） ? 任何一個(gè) NFA識(shí)別的語(yǔ)言，可以表示為一個(gè)正規(guī)表達(dá)式 – 拓廣狀態(tài)轉(zhuǎn)換圖的概念，轉(zhuǎn)移符號(hào)可以用一個(gè)正規(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?，它只有一個(gè)初始狀態(tài) X和一個(gè)終止?fàn)顟B(tài) Y。 88 2. 反復(fù)應(yīng)用以下三條規(guī)則，消去 ?NFA M?中的狀態(tài)結(jié)點(diǎn)和弧，直至只剩下?tīng)顟B(tài)結(jié)點(diǎn) X、 Y及連接二者 的弧。在消去的過(guò)程中，用正規(guī)表達(dá)式標(biāo)記弧。 1 2 3 1 3 r1 r2 r1r2 1 2 r1 r2 1 2 r1 | r2 1 2 3 r1 r3 r2 1 3 r1(r2)*r3 ? ? ? 89 3. 連接 X、 Y結(jié)點(diǎn)邊的標(biāo)記 r即為所求的正規(guī)表達(dá)式： X Y r start 90 每次減少一個(gè)中間狀態(tài) iq q jqa bcdiq jqdae * bce *dce *bae *e91 最后的正規(guī)表達(dá)式 r1*r2(r4|r3r1*r2)* 0q fq1r2r3r4r92 1 5 4 3 2 r s v w t u (1) 1 5 4 3 2 r s v w t | u (2) 1 2 5 4 r(t | u)*v s(t | u)*w s(t | u)*v r(t | u)*w (3) 消除狀態(tài) 3 93 例：給出下圖對(duì)應(yīng)的正規(guī)表達(dá)式。 q0 q2 q1 1 1 2 0 94 第 1步，增加狀態(tài) q和 f，構(gòu)造 ?NFA： q0 q2 q1 1 1 2 0 q ? f ? ? ? 95 q0 q2 2 0 q ? f ? ? 2|11*2 11* 消除狀態(tài) q1得到： 96 消除狀態(tài) q2得到： q0 0 q ? f ((11*)|((2|11*2)2*) ? 97 消除狀態(tài) q0得到： q f ?|0*((11*)|((2|11*2)2*) 化簡(jiǎn)得： 0*1*2* 98 Eg. All strings of 1s and 0s that contains at most two 0s q0 q2 q1 0 1 0 1 1 q0 q2 q1 0 1 0 1 1 q f ? ? ? ? 99 Elimiate state q2 Elimiate state q1 q0 q1 0 1 1 q f ? ?|01* ? q0 1 q f ? ?|01*(?|01*) 100 Elimiate state q0 q f q0 1 q f ? ?|01*(?|01*) 1*(?|01*(?|01*)) 至多包含兩個(gè) 0的 01字符串： 1*(?|01*(?|01*)) 101 Eg. All strings of 1s and 0s that do not contains three 0s (1*(?|01|001)1*)*(?|0|00) q0 q2 q1 0 1 0 1 1 102 給出偶數(shù)個(gè) 0和偶數(shù)個(gè) 1的字符串的正規(guī)表達(dá)式 3 1 2 0 1 1 1 1 0 0 0 0 start 偶 0偶 1 奇 0奇 1 奇 0偶 1 偶 0奇 1 103 消除 狀態(tài) 1： 3 2 0 11 10 1 1 01 0 0 start 00 104 消除 狀態(tài) 2： 3 0 11|00 10|01 01|10 start 00|11 105 消除 狀態(tài) 3： 0 11|00 (10|01)(00|11)*(01|10) start q f ((00|11)|((10|01)(00|11)*(01|10))* 即： start 106 習(xí)題 ? b) d) ? ? ? a) b)
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1