蔣立源編譯原理第三版第三章習(xí)題與答案(修改后)

1、第 3 章習(xí)題3-1 試構(gòu)造一右線性文法，使得它與如下的文法等價(jià)4ab a f ut u fau|a d fbt|b b fcb|c 并根據(jù)所得的右線性文法，構(gòu)造出相應(yīng)的狀態(tài)轉(zhuǎn)換圖。3-2 對(duì)于如題圖3-2 所示的狀態(tài)轉(zhuǎn)換圖題圖 3-2 (1) 寫(xiě)出相應(yīng)的右線性文法；(2) 指出它接受的最短輸入串；(3) 任意列出它接受的另外4 個(gè)輸入串 ; (4) 任意列出它拒絕接受的4 個(gè)輸入串。3-3 對(duì)于如下的狀態(tài)轉(zhuǎn)換矩陣: aba bsassabaabab abbbbbb(i )初態(tài) :s 終態(tài)b(込)初態(tài)：s 終態(tài) :baba bsabsasacaa c bbbcbb ccccccc(ii )初態(tài)

2、：s 終態(tài)a,c(iv)初態(tài):s 終態(tài)：c題圖 3-3(1) 分別畫(huà)出相應(yīng)的狀態(tài)轉(zhuǎn)換圖；(2) 寫(xiě)出相應(yīng)的3 型文法；(3) 用自然語(yǔ)言描述它們所識(shí)別的輸入串的特征3-4 將如下的 nfa 確定化和最小化：題圖 3-4 3-5 將如題圖 3-5 所示的具有 &動(dòng)作的nfa 確定化。3-8 構(gòu)造與正規(guī)式 (a|b) *(aa|bb)(a|b) *相應(yīng)的 dfa題圖 3-5 具有 &動(dòng)作的nfa3-6 設(shè)有文法 gs :s aa a aa|bb 試用正規(guī)式描述它所產(chǎn)生的語(yǔ)言。3-7 分別構(gòu)造與如下正規(guī)式相應(yīng)的nfa(0 * |1)(1 *0)* (2) b|a(aa *b)*b4

3、bb|cc|c c cc|c 第 3 章習(xí)題答案3-1 解：根據(jù)文法知其產(chǎn)生的語(yǔ)言是：lg=a monc | m,n,i 仝 1 可以構(gòu)造與原文法等價(jià)的右線性文法：4 aa aa|bb 4 bb|cc|c c cc|c3-2 解：(1)其對(duì)應(yīng)的右線性文法是ga:a f 0d 4 0a|1c ?0b|1c ef 0b|1c 最短輸入串為011(3) 任意接受的四個(gè)輸入串為：0110,0011,000011,00110 (4) 任意拒絕接受的輸入串為：0111 , 1011 , 1100 , 1001 3-3 解：(1)相應(yīng)的狀態(tài)轉(zhuǎn)換圖為:其狀態(tài)轉(zhuǎn)換圖如下：cf 0a|1f|1 ff 1a|0e|

4、0 與( i )相應(yīng)的狀態(tài)轉(zhuǎn)換圖相應(yīng)的 3 型文法為：(i ) s aa|bs aa|bb| b (ii) s aa|bb| aa ba|ac| a|b4ab|bc| b c ac|bc|a|b4 ab|bb|a|b (iii) s aa|bb| ba ab|ba| a4ab| bb|a|b(v) s bs|aaa ac|bb| a4ab|bc| bc ac|bc|a|b(3)用自然語(yǔ)言描述的輸入串的特征為：(i )以任意個(gè)(包括 0 個(gè))b 開(kāi)頭，中間有任意個(gè)(大于1) a, 跟一個(gè) b, 還可以有一個(gè)由 a,b 組成的任意字符串。(ii) 以 a 打頭， 中間有任意個(gè) ( 包括 0 個(gè))

5、b,再跟 a,最后由一個(gè)a,b 所組成的任意串結(jié)尾；或者以 b 打頭，中間有任意個(gè)( 包括 0 個(gè)) a,再跟 b,最后由一個(gè)a,b 所組成的任意串結(jié)尾。(iii) 以 a 打頭，后跟任意個(gè) ( 包括 0 個(gè)) b , 再跟 a, 最后由一個(gè)a,b 所組成的任意串結(jié)尾；或者以 b 打頭，由一個(gè)a,b 所組成的任意串結(jié)尾。(iv) 以任意個(gè) ( 包括 0 個(gè)) b 開(kāi)頭,中間跟 aa, 最后由一個(gè)a,b 所組成的任意串結(jié)尾；或者以任意個(gè) ( 包括0 個(gè))b 開(kāi)頭，中間跟ab 后，再接任意個(gè)( 包括0 個(gè)) a, 再接 b, 最后由一個(gè)a,b所組成的任意串結(jié)尾。3-4 解：將 nfa m 確定化后

6、得dfa m ，其狀態(tài)轉(zhuǎn)換矩陣如答案圖34(1) 之(a)所示，給各狀態(tài)重新命名，即令：s=1, s,a=2, a,b=3, b=4 且由于 3 及 4 的組成中均含有m 的終態(tài) b, 故 3 和 4 組成了dfa m 的終態(tài)集 z。于 是，所構(gòu)造之 dfam 的狀態(tài)轉(zhuǎn)換矩陣和狀態(tài)轉(zhuǎn)換圖如答案圖3-4-(1) 之(b)及(c)所示。此時(shí)子集已全部分裂，故最小化的過(guò)程宣告結(jié)束, m 即為狀態(tài)數(shù)最小的dfaa b a bss,a12s,as；,a a,b 2 2 3a,bb a,b343bb44初態(tài) : s終態(tài) :a,b,b初態(tài) :1終態(tài) :3,4現(xiàn)將 dfa m 最小化：(i )初始分劃由兩個(gè)子

7、集組成，即n。：1,2, 3,4 (ii)為得到下一分劃，考察子集1,2 o因?yàn)? b =3 3,4 但 1 b = 故 1 和 2 可區(qū)分，于是便得到下一分劃n i： 1, 2, 3,4 (iii)又因n 1工n o , 再考慮 3,4 ，因?yàn)? b =3 3,4 而 4 b = 故 3 和 4 可區(qū)分，從而又得到n 2： 1, 2, 3, 4此時(shí)子集已全部分裂，故最小化的過(guò)程宣告結(jié)束, m 即為狀態(tài)數(shù)最小的dfa(2)將 nfa m 確定化后得dfa m ，其狀態(tài)轉(zhuǎn)換矩陣如答案圖3-4-(2) 之(a)所示 , 給各狀態(tài)重新命名，即令：s=1, a=2, b,c=3 且由于 3 的組成中含

8、有m 的終態(tài) c,故 3 為 dfam 的終態(tài)。于是，所構(gòu)造之dfam 的狀態(tài)轉(zhuǎn)換矩陣和狀態(tài)轉(zhuǎn)換圖如答案圖3-4-(2) 之(b)及(c)所示。a ba bsa12a e,c a2 3 2b,ca32初態(tài) :s 終態(tài) :b,c 初態(tài):1 終態(tài) :3 (a)確定化后的狀態(tài)矩陣(b)改名后的狀態(tài)矩陣(c) dfa m 的狀態(tài)轉(zhuǎn)換圖答案圖 3-4-(2) 現(xiàn)將 dfa m 最小化：(i )初始分劃由兩個(gè)子集組成，即n。：1,2, 3 (ii)為得到下一分劃，考察子集1,2 o因?yàn)? b =2 1,2 但 1 b = 故 1 和 2 可區(qū)分，于是便得到下一分劃n 1: 1, 2, 3將 nfa m 確

9、定化后得dfa m ，其狀態(tài)轉(zhuǎn)換矩陣如答案圖3-4-(3) 之(a)所示 , 給各狀態(tài)重新命名，即令: s=1, a=2, s,b=3 且由于 3 的組成中含有m 的終態(tài) b, 故 3 為 dfam 的終態(tài)。于是，所構(gòu)造之狀態(tài)轉(zhuǎn)換矩陣和狀態(tài)轉(zhuǎn)換圖如答案圖3-4-(3) 之(b)及(c)所示。a ba bsa12as,b23s,ba32初態(tài):s 終態(tài):s,b 初態(tài) :1 終態(tài) :3 (a)確定化后的狀態(tài)矩陣(b)改名后的狀態(tài)矩陣(c) dfa m 的狀態(tài)轉(zhuǎn)換圖答案圖 3-4-(3) 現(xiàn)將 dfa m 最小化：(i )初始分劃由兩個(gè)子集組成，即n。：1,2, 3 (ii)為得到下一分劃，考察子集1

10、,2 o因?yàn)? b =3 但 1 b = 故 1 和 2 可區(qū)分，于是便得到下一分劃n 1: 1, 2, 3 dfam 的此時(shí)子集已全部分裂，故最小化的過(guò)程宣告結(jié)束, m 即為狀態(tài)數(shù)最小的dfa(4)將 nfa m 確定化后得dfa m ，其狀態(tài)轉(zhuǎn)換矩陣如答案圖3-4-之(a)所示 , 給各狀態(tài)重新命名，即令：a=1, b,c=2, b=3, c=4 且由于 2 和 4 的組成中含有m 的終態(tài) c,故 2 和 4 組成了dfa m 的終態(tài)集 z。于是 , 所構(gòu)造之 dfa m 的狀態(tài)轉(zhuǎn)換矩陣和狀態(tài)轉(zhuǎn)換圖如答案圖3-4-(4) 之(b)及(c)所示。ab abab,cb12 3b,cac21 4

11、ba3 1cac41 4初態(tài) :a終態(tài) b,c,c初態(tài) :1 終態(tài):2,4(a)確定化后的狀態(tài)矩陣(b)改名后的狀態(tài)矩陣(c) dfa m 的狀態(tài)轉(zhuǎn)換圖答案圖 3-4-(4) 現(xiàn)將 dfa m 最小化：(i )初始分劃由兩個(gè)子集組成，即n。：1,3, 2,4 (ii) 為得到下一分劃，考察子集1,3 o因?yàn)?a=2 2,4 但 3 a=1 1,3 故 1 和 3 可區(qū)分，于是便得到下一分劃n i： 1, 3, 2,4 (iii) 又因n 1工n o, 再考慮 2,4 ，因?yàn)? a =4 a =1, 2 b =4b =4 所以 2 和 4 不可區(qū)分，故子集s,b 已不能再分裂。此時(shí)n 2 =n

12、1 , 子集分裂的過(guò)程宣告結(jié)束。(iv )現(xiàn)選擇狀態(tài)2 作為 2,4 的代表，將狀態(tài)4 從狀態(tài)轉(zhuǎn)換圖中刪去，并將原來(lái)引至 4 的矢線都引至2, 這樣，我們就得到了最小化后的dfa m 如答案圖 3-4-之(d)所示。a a b a (d) 3-5 解：(1)將具有 &動(dòng)作的 nfam 確定化后得dfam ，其狀態(tài)轉(zhuǎn)換矩陣如答案圖3-5-(1)之(a)所示，給各狀態(tài)重新命名，即令：s,b,c=1, a=2, b,c =3, c=4 且由于 1,3 和 4 的組成中均含有m 的終態(tài) c,故 1,3 和 4 組成了dfa m 的終態(tài)集 z。 于是，所構(gòu)造之dfa m 的狀態(tài)轉(zhuǎn)換矩陣和狀態(tài)轉(zhuǎn)換

13、圖如答案圖3-5-(1) 之(b)及(c)所示。ab ca b cs,b,cab,c12 3ac2 4b,cb,c33c4初態(tài) :s終態(tài) : s,b,c,b,c ,c初態(tài) :1 終態(tài):1,3,4答案圖 3-5-(1) (2)將具有 &動(dòng)作的 nfam 確定化后得dfam , 其狀態(tài)轉(zhuǎn)換矩陣如答案圖3-5-(2)之(a)所示，給各狀態(tài)重新命名，即令：s=1, z=2, r,u =3, s,x=4, r,u,y=5, s,u,x=6, s,z=7, r,u,y,z=8 且由于 2,7 和 8 的組成中均含有m 的終態(tài)乙故 2,7 和 8 組成了dfa m 的終態(tài)集 z。 于是，所構(gòu)造之df

14、a m 的狀態(tài)轉(zhuǎn)換矩陣和狀態(tài)轉(zhuǎn)換圖如答案圖3-5-(2) 之(b)及(c)所示。s z r,u z r,u s,x z s,x z r,u,y r,u,y s ,x,u z s,u,x z,s r,u,y,z s,z z r,u r,u,y,z s,x,u z 初態(tài) :s 終態(tài) :z,s,z,r,u,y,z 初態(tài) :終態(tài) :2,7,8 確定化后的狀態(tài)矩陣(b)改名后的狀態(tài)矩陣答案圖 3-5-(2) 3-6 解:首先將文法寫(xiě)成方程組：s=aa a=aa+bb (2) b=bb+cc+c c=cc+c (4) 將代入，得：b=bb+c (5) 由論斷 3.1，方程的解為：c=c*c 將上式代入 (

15、5)，得：b=bb+c *c 由論斷 3.1，得：* * b=bc c 將上式代入 (2)，得：a=aa+b bc c 由論斷 3.1，得：* * * a=a b bc c 將上式代入 (1)，得：* * * s=aab bc c 即文法所產(chǎn)生的語(yǔ)言可用正規(guī)式a*ab*bc*c 表示。3-7 解：(1)構(gòu)造與正規(guī)式(0* |1)(1 *0) *相應(yīng)的 nfa 的步驟如答案圖3-7-(1) 所示 :(0*|1) (1*0) 答案圖3-7-(1) 正規(guī)式(0*1 1 ) ( 1* 0 ) )* 的 nfa 構(gòu)造與正規(guī)式b|a(aa *b)*b 相應(yīng)的 nfa 的步驟如答案圖3-7-(2) 所示 :

16、 a ( a a* b )* b 答案圖 3-7-(2) 正規(guī)式 b|a(aa *b)*b 的 nfa 3-8 解:首先，構(gòu)造與正規(guī)式(a|b) *(aa|bb)(a|b) *相應(yīng)的 nfaim 其構(gòu)造步驟如答案圖3-8(a) 所示 : 其次，將答案圖3-8(a) 所示的具有 &動(dòng)作的nfam 確定化后得到dfam ，其狀態(tài)轉(zhuǎn)換矩陣如答案圖3-8(b) 所示，給各狀態(tài)重新命名，即令：s,3,1=s, 3,1,5=a, 3,1,6 =b, 3,1,5,2,4,z=c, 3,1,6,2,4,z=d, 3,1,6,4,z=e, 3,1,5,4,z=f 且由于 c,d,e 和 f 的組成中均含

17、有nfa m 的終態(tài) z, 故 c,d,e 和 f 組成了dfa m 的終 態(tài)集z。于是，將nfa m 確定化后所得dfa m 的狀態(tài)轉(zhuǎn)換矩陣和狀態(tài)轉(zhuǎn)換圖如答案圖 3-8(c) 及(d)所示。答案圖 3-8 (a) 正規(guī)式 (a|b) (aa|bb)(a|b) * 的 nfa m (a|b)* aa|bb * 3,1,624z,3,164,z,3,1,5,4,z (c)改名后的狀態(tài)矩陣ab a bs,3,13,1,53,1,6sab3,1,53,1,5,2,4,z3,1,6 a c b3,1,6 3,1,5 3,1,6,2,4,z b a d3,1,5,2,4,z3,1,5,2,4,z3,1,

18、6,4,zcce3,1,6,2,4,z3,1,5,4,z3,1,6,2,4,zdfd3,1,6,4,z3,1,5,4,z3,1,6,2,4,zefd3,1,5,4,z3,1,5,2,4,z3,1,6,4,zfce初態(tài) :s,3,1 終態(tài)：3,1,5,2,4,z, 初態(tài) :s 終態(tài)：c,d,e,f (b)確定化后的狀態(tài)矩陣a 答案圖 3-8 最后，將所得dfa m 最小化：(i )初始分劃由兩個(gè)子集組成，即n o：s ab, c,d,e,f (ii) 為得到下一分劃，考察子集s,a,b 。因?yàn)閟,b a =a sab 但 a a=c c,d,e,f 故 s,b 和 a 可區(qū)分，于是便得到下一分劃n i： s,b, a, c,d,e,f (iii) 因n i工n 0 , 考慮 s,b ，因?yàn)閟b=b s,b 但 b b=d c,d,e,f 故 s 和 b 可區(qū)分，于是便得到下一分劃n 2： s, b, a, c,d,e,f (iv) 又因n 2工n 1 , 再考慮 c,d,e,f ，因?yàn)閏