編譯原理第4章答案

1、編譯原理第 4 章答案編譯原理習(xí)題解答第 1/1 頁(yè)第 4 章詞法分析1。構(gòu)造對(duì)應(yīng)于以下標(biāo)準(zhǔn)公式的 DFA:(1) 1 (0 | 1)* 101(2)1(1010 * | 1(010)* 1)* 0(3)a(a | b)* | ab * a)* b(4) b(ab)| bb)ab 溶液：(1)1(0 | 1)對(duì)應(yīng)于101的NFA是256 1990 11 1下表通過子集方法將 NFA 轉(zhuǎn)換為 DFA:I A D E B1D B C E B C E F G H I J K L M N I 0 二毛 閉包(MoveTo(l,0)C10E H J L J M N D B F D I K I D B F

2、 O4B1 L 1 0 I 1H 0K 0J 0 0a 1 B 0MC1 1101 n(3)a(a | B)* | ab * a)* B(略) NFA=(x，y, z，0，1)是已知的。m, x，z)其中:m (x, 0) = z， m (y， 0) = x， y， m (z， 0) = x， z， m (x， 1) = x ， m (y， 1) = ,m (z, 1) = y，構(gòu)造相應(yīng)的DFA解決方案:根據(jù)NFA圖，下 列1x 0 z 0 1 00y編譯原理問題解決第3頁(yè)/3下表通過子集方法將 NFA 轉(zhuǎn)換為 DFA:IA C B A C B B I1 =-閉包Moveto (I ,1) c

3、 c d ed e 5£ 4 d £ 6 d下表通過子集方法將 NFA轉(zhuǎn)換為DFA:id =-閉包(移動(dòng)到(I, d)B E E7E le =£ C C E -閉包1(移動(dòng)到(I,E)ls =-閉包(移動(dòng)到(I, s)F6l .=-閉包(移動(dòng)到(I ,s) )D D A B C D E F D B D S ？aA|bQ A？aA|bB|b B？bD|aQ Q？aQ | bD | b D？bB|aA E?男 |女？ Bd | AE | bdgd7。為文法g構(gòu)造相應(yīng)的最小DFA:解決方案:由于沒有來自S的輸入字符串能夠到達(dá)狀態(tài)E和F,狀 態(tài) E 和 F 是多余的，將不

4、被考慮。這樣， NFA:AA S A B A B Z B Q A B B B B B B D 編譯原理練習(xí)解答第 7/7頁(yè)下表通過子集方法將 NFA 轉(zhuǎn)換為 DFA:I 1S2A3Q4B ， Z 5 D ， Z 6 D 7 B 。從上表可以看出 :(1)因?yàn)?4， 5 是 DFA 的最終狀態(tài)， 所以其他的是非最終狀態(tài)。 狀態(tài) 集可以分為兩個(gè)子集 :P1 = 1， 2， 3， 6， 7， P2 = 4， 5在P1，因?yàn)?, 3是輸入B后的最終狀態(tài)，1, 6, 7是輸入B后 的非最終狀態(tài)，所以 P1 可以分為P1=1 = 1 , 6, 7, P12=2, 3(3)在P11，1和6中同樣，1和7也不

5、等同因此P11可分為：P111=1, p112 = 6, 7(4)查 p112 = 6，7 。因?yàn)檩斎?a 是 2，3，所以 6，7 的等價(jià)性由 2， 3 的等價(jià)性決定(5) 檢查 P12 = 2 ，3 。由于輸入 B 是 4，5， 2， 3 是否相等取決于 4， 5 是否相等(6) 檢查 p2 = 4 ，5 ，顯然 4，5 是否相等取決于 2，3 和 6，7 是否 同時(shí)相等因?yàn)榇嬖?(4)，也就是說， 6 和 7 是否相等取決于 2 和 3 是否 相等， 4 和 5 是否相等取決于 2 和 3 是否相等。因?yàn)榇嬖?(5)，也就是 說，2 和 3 是否相等取決于 4 和 5 是否相等，所以存在

6、 4 和 5 個(gè)相等、 2 和 3 個(gè)相等以及 6 和 7 個(gè)相等(7) 刪除上表中的第 3、5 和 7 行，并將剩余行中的第 3、 5 和 7 行 更改為相應(yīng)的等效狀態(tài) 2、4 和 6。下表可用 :1 1S2A4B ， Z 6D 可以通過這種方式最小化的 DFA 如下 :1 B2A2A2A2Aa2 A 6 B B 4 la 2A4B, Z6D6Dlb la =-閉 &包 (移動(dòng)到 (1 ， a) 2A 2A 3Q 給出對(duì)應(yīng)于下列語(yǔ)法的標(biāo)準(zhǔn)公式 :S？1B？ 1S|1 B？0s | 0s = 01 | 01s = 10 | 10s具有 :s = 01s | 10s | 01 | 10

7、=(01 | 10)s |(01 | 10)=(01|10)(01|10)即 (01 |10)(01 | 10)是所需的常規(guī)公式溶液:將后兩個(gè)生產(chǎn)配方代入第一個(gè)生產(chǎn)配方為9。最小化圖4.18的DFA，它所識(shí)別的語(yǔ)言由正常公式描述1a c 3 d c 6 5 b1a b 7 b解決方案：2 a 4圖4.18（1）因?yàn)?6，7 是 DFA 的最終狀態(tài)， 而其他是非最終狀態(tài)， 所以狀態(tài) 集可以被分成兩個(gè)子集 ：P1 = 1，2，3，4，5，p2 = （2）因?yàn)?F（6， b）=F（7，b）=6 和 6，7 沒有其他輸入，所以 6，7 是等 價(jià)的（3）因?yàn)?f （3，c） = f （4，c） = 3，

8、f （3，d） = f （4，d） = 5，f （3，b） = 6， f （4，b） = 7，和6，7是等價(jià)的，所以 3，4是等價(jià)的（1 ）因?yàn)?f （1，b） =f （2，b） = 2，f （1，a） = 3，f （2，a） = 4，和3，4是等價(jià)的，所以 1，2 是等價(jià)的 （2）狀態(tài) 5 不等于 1、2、3、4，因?yàn)闆]有輸入字符 B。（3）綜上所述，上圖中的 DFA 狀態(tài)可分為 ：p = 1 ，2 、3 ，4 、5 、 6，7DFA 以標(biāo)準(zhǔn)形式表示為 ：B1 a c 3d a b 65 bb * a（c | da）* bb *10。構(gòu)造以下語(yǔ)法的自動(dòng)機(jī) ：？A0 A ？ A0|S 1 |0這個(gè)自動(dòng)機(jī)確定嗎？如果你不確定，一定要確定。自動(dòng)機(jī)的相應(yīng) 語(yǔ)言是什么？由于這種語(yǔ)法的生成式？ A0，A ？A0|S1 沒有字符集 VT 的輸入， 所以它不是一個(gè)確定的自動(dòng)機(jī)。 為了確定其他公式， 必須使用替換法 來獲得其相應(yīng)的正規(guī)公式。放s。A0被代入得到的公式a。S1有:A=A0|A01|0二A(0|01)|0=0(0|01)替換 s ？ AO 有語(yǔ)法的正規(guī)形式:0(0|01)0，所以，重寫語(yǔ)法確