蔣立源編譯基本知識(shí)第三版第三章知識(shí)題與答案解析(修改后)

1、第3章習(xí)題3-1試構(gòu)造一右線性文法，使得它與如下的文法等價(jià)U f aU|aD f bT|b B f cB|c并根據(jù)所得的右線性文法，構(gòu)造出相應(yīng)的狀態(tài)轉(zhuǎn)換圖。3-2 對(duì)于如題圖3-2所示的狀態(tài)轉(zhuǎn)換圖b寫出相應(yīng)的右線性文法;指出它接受的最短輸入串;任意列出它接受的另外 4個(gè)輸入串;任意列出它拒絕接受的 4個(gè)輸入串。3-3對(duì)于如下的狀態(tài)轉(zhuǎn)換矩陣:分別畫出相應(yīng)的狀態(tài)轉(zhuǎn)換圖;寫出相應(yīng)的3型文法;用自然語(yǔ)言描述它們所識(shí)別的輸入串的特征。3-4將如下的NFA確定化和最小化:bB繰圖:H3-5 將如題圖3-5所示的具有動(dòng)作的NFA確定化。題圖3-5具有動(dòng)作的NFA3-6設(shè)有文法GS:A f aA|bBB f

2、bB|cC|cCf cC|c試用正規(guī)式描述它所產(chǎn)生的語(yǔ)言。3-7分別構(gòu)造與如下正規(guī)式相應(yīng)的NFA。3-8構(gòu)造與正規(guī)式(a|b) *(aa|bb)(a|b) *相應(yīng)的DFA。(1) (0 |1)(1 0) b|a(aa *b)*b第3章習(xí)題答案3-1 解：根據(jù)文法知其產(chǎn)生的語(yǔ)言是LG=a mbnci| m,n,i i=1可以構(gòu)造與原文法等價(jià)的右線性文法A f aA|bBB f bB|cC|cCf cC|c其狀態(tài)轉(zhuǎn)換圖如下：3-2 解:(1)其對(duì)應(yīng)的右線性文法是GA:A f ODBf 0A|1CCf 0A|1F|1Df 0B|1CEf 0B|1CFf 1A|0E|0最短輸入串為011任意接受的四個(gè)

3、輸入串為:0110,0011,000011,00110任意拒絕接受的輸入串為:0111 , 1011 , 1100 , 10013-3解:(1)相應(yīng)的狀態(tài)轉(zhuǎn)換圖為:baa, b與（i ）相應(yīng)的狀態(tài)轉(zhuǎn)換圖a, b與（iii）相應(yīng)的狀態(tài)轉(zhuǎn)換圖（2）相應(yīng)的3型文法為:(i ) Sf aA|bSA f aA|bB|bB f aB|bB|a|b(ii) Sf aA|bB|aAf bA|aC|a|bB f aB|bC|bCf aC|bC|a|b(iii) S f aA|bB|bA f aB|bA|aBf aB|bB|a|b(iv) S f bS|aAA f aC|bB|aB f aB|bC|bCf aC|

4、bC|a|b（3）用自然語(yǔ)言描述的輸入串的特征為:a，跟一個(gè)b，還可以有（i ）以任意個(gè)（包括0個(gè)）b開頭，中間有任意個(gè)（大于 1）一個(gè)由a,b組成的任意字符串。（ii）以a打頭，中間有任意個(gè)（包括 0個(gè)）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è)(包括尾；或者以任意個(gè)(包括再接 b,最后由一個(gè) a,b所組成的任意串結(jié)尾。3-4解：0個(gè)

5、)b開頭沖間跟aa，最后由一個(gè)a,b所組成的任意串結(jié) 0 個(gè)) b 開頭,中間跟 ab 后,再接任意個(gè)(包括 0 個(gè)) a,(1)將NFA M確定化后得DFA M ，其狀態(tài)轉(zhuǎn)換矩陣如答案圖3-4-(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)造之DFA M 的狀態(tài)轉(zhuǎn)換矩陣和狀態(tài)轉(zhuǎn)換圖如答案圖3-4-(1)之(b)及(c)所示。SS,AS,AS,AA,BA,BBA,BBB初態(tài):S終態(tài)：A,B,B初態(tài):1終態(tài):3,4答案圖34(1)現(xiàn)將DFA M 最小化:(i )初始分劃由

6、兩個(gè)子集組成，即(ii )為得到下一分劃，考察子集1,2。因?yàn)?b =33,4 1b =和2可區(qū)分，于是便得到下一分劃n: 1, 2, 3,4(iii)又因n1工n，再考慮3,4，因?yàn)?b =33,4 4b =故3和4可區(qū)分，從而又得到n: 1, 2, 3, 4此時(shí)子集已全部分裂，故最小化的過(guò)程宣告結(jié)束，M 即為狀態(tài)數(shù)最小的DFA。將NFA M確定化后得DFA M ，其狀態(tài)轉(zhuǎn)換矩陣如答案圖3-4-(2)之(a)所示, 給各狀態(tài)重新命名，即令:S=1,A=2,B,C=3且由于3的組成中含有 M的終態(tài)C,故3為DFA M 的終態(tài)。于是，所構(gòu)造之DFA M 的狀態(tài)轉(zhuǎn)換矩陣和狀態(tài)轉(zhuǎn)換圖如答案圖34(2

7、)之(b)及(c)所示。終態(tài):3(c) DFA M 的狀態(tài)轉(zhuǎn)換圖ababSA12A E,CA232B,CA32初態(tài)：S 終態(tài):B,C初態(tài):1答案圖3-4-(2)現(xiàn)將DFA M 最小化:(i )初始分劃由兩個(gè)子集組成，即n:1,2, 3(ii )為得到下一分劃，考察子集1,2。因?yàn)?b =2 1,2 1b故1 和2可區(qū)分，于是便得到下一分劃n： 1, 2, 3此時(shí)子集已全部分裂，故最小化的過(guò)程宣告結(jié)束，M 即為狀態(tài)數(shù)最小的DFA。將NFA M確定化后得DFA M ，其狀態(tài)轉(zhuǎn)換矩陣如答案圖3-4-(3)之(a)所示, 給各狀態(tài)重新命名，即令：S=1,A=2,S,B=3且由于3的組成中含有 M的終態(tài)

8、B,故3為DFA M 的終態(tài)。于是，所構(gòu)造之DFA M 的狀態(tài)轉(zhuǎn)換矩陣和狀態(tài)轉(zhuǎn)換圖如答案圖3-4-(3)之(b)及(c)所示。ababSA12AS,B23S,BA32初態(tài)：S 終態(tài)：S,B初態(tài):1 終態(tài):3(a) 確定化后的狀態(tài)矩陣(b) 改名后的狀態(tài)矩陣a(c) DFA M 的狀態(tài)轉(zhuǎn)換圖答案圖3-4-(3)現(xiàn)將DFA M 最小化:(i )初始分劃由兩個(gè)子集組成，即(ii )為得到下一分劃，考察子集1,2。因?yàn)?b =3 1b =故1和2可區(qū)分，于是便得到下一分劃n： 1, 2, 3此時(shí)子集已全部分裂，故最小化的過(guò)程宣告結(jié)束，M 即為狀態(tài)數(shù)最小的DFA。將NFA M確定化后得DFA M ，其狀

9、態(tài)轉(zhuǎn)換矩陣如答案圖3-4-(4)之(a)所示,給各狀態(tài)重新命名，即令:A=1,B,C=2,B=3,C=4所構(gòu)造之DFA M且由于2和4的組成中含有 M的終態(tài)C,故2和4組成了 DFA M 的終態(tài)集Z。于是,的狀態(tài)轉(zhuǎn)換矩陣和狀態(tài)轉(zhuǎn)換圖如答案圖3-4-(4)之(b)及(C)所示。(a) 確定化后的狀態(tài)矩陣(b) 改名后的狀態(tài)矩陣ababAB,CB123B,CAC214BA3 1CAC414初態(tài):A1終態(tài):B,C,C初態(tài):1 終態(tài):2,4aaba(c) DFA M 的狀態(tài)轉(zhuǎn)換圖(d) 對(duì)DFA M最小化后所得DFA M的狀態(tài)轉(zhuǎn)換圖答案圖3-4-(4)現(xiàn)將DFA M 最小化:(i )初始分劃由兩個(gè)子集

10、組成，即(ii )為得到下一分劃，考察子集1,3。因?yàn)?a =22,4 3a =1 1,3故1和3可區(qū)分，于是便得到下一分劃n: 1, 3, 2,4(iii)又因n1工n，再考慮2,4，因?yàn)?a =4 a =1,2b =4 b =4所以2和4不可區(qū)分，故子集S,B已不能再分裂。此時(shí)n 2 = n1 ,子集分裂的過(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-(4)之(d)所示。3-5 解:(1)將具有動(dòng)作的NFA M確定化后得DFA M 其狀態(tài)轉(zhuǎn)換矩陣如答案圖3-5-(1)之

11、(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)換圖如答案圖3-5-(1)之(b)及(c)所示。abca b cS,B,CAB,C1AC24B,CB,C3C42初態(tài):S終態(tài)：S,B,C,B,C,C初態(tài):1 終態(tài):1,3,4(a) 確定化后的狀態(tài)矩陣(b) 改名后的狀態(tài)矩陣(c) DFA M 的狀態(tài)轉(zhuǎn)換圖答案圖3-5-(1)(2)將具有動(dòng)作的NFA M確定化后得DFA M 其狀態(tài)轉(zhuǎn)換矩陣如答案圖 3-5-(2)之(a)所示，給各

12、狀態(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)Z,故2,7和8組成了 DFA M 的終態(tài)集Z 。于是，所構(gòu)造之DFA M 的狀態(tài)轉(zhuǎn)換矩陣和狀態(tài)轉(zhuǎn)換圖如答案圖3-5-(2)之(b)及(c)所示。SZR,UZR,US,XR,U, YS,U,XS,ZR,U, YZ初態(tài):S,XZZSXUZ,SR,U, YZR,U, YZZR,US,X,UZ終態(tài):Z,S,Z,R,U,YZ初態(tài):終態(tài):2,7,8確定化后的狀態(tài)矩陣(b)改名后的狀態(tài)矩陣答案圖3-5-(2)3-6 解:首先將文法寫成方程組

13、:(1)S=aAA=aA+bBB=bB+cC+cC=cC+c將代入，得:(5)B=bB+C由論斷3.1，方程的解為:C=c*c將上式代入(5)，得:由論斷 3.1 ，得： * *B=b *c*c將上式代入 (2) ，得：A=aA+b *bc*c由論斷 3.1 ，得：A=a *b *bc *c將上式代入 (1) ，得：* * * S=a *ab *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) 所示：S(0*|1) (1*0)答案圖 3-7-(1) 正規(guī)式(0*1

14、1 ) ( 1* 0 ) )* 的NFA構(gòu)造與正規(guī)式 b|a(aa*b)*b相應(yīng)的NFA的步驟如答案圖3-7-(2)所示:答案圖3-7-(2) 正規(guī)式b|a(aa *b) *b的NFA3-8 解:首先，構(gòu)造與正規(guī)式(a|b) *(aa|bb)(a|b) *相應(yīng)的NFA M，其構(gòu)造步驟如答案圖3-8(a)所示:S-0 (a|b)0 aa|bb3aabb2(a|b)*MBb3aa56bbJ 4a答案圖3-8 (a)正規(guī)式(a|b) (aa|bb)(a|b) 的 NFA M其次，將答案圖3-8(a)所示的具有動(dòng)作的NFA M確定化后得到DFA M 其狀態(tài)轉(zhuǎn)換矩陣如答案圖3-8(b)所示，給各狀態(tài)重新

15、命名，即令:S,3,1=S,3,1,5=A,3,1,6 =B,3,1,524Z=C,3,1,624,Z=D,3,1,6,4,Z=E,3,1,5,4,Z=F且由于C,D,E和F的組成中均含有 NFA M 的終態(tài) 乙故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)所示。aba bS,3,13,1,53,1,6SAB3,1,53,1,5,2,4,Z3,1,6a C B3,1,63,1,53,1,6,2,4,ZB A D3,1,5,2,4,Z3,1,5,2,4,Z3,1,6,4,ZCCE3,1,6,2

16、,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)矩陣(C)改名后的狀態(tài)矩陣abBAabbaabab(d)DFA M 的狀態(tài)轉(zhuǎn)換圖3,1,624Z,3,164Z,3,1,5,4Z答案圖 3-8最后，將所得DFA M 最小化:(i )初始分劃由兩個(gè)子集組成，即n:S,A,B, C,D,E,F(ii )為得到下一分劃，考察子集S,A,B。因?yàn)镾,Ba =AS,A,B Aa =C C,D,E,F故S,B和A可區(qū)分，于是便得到下一分劃n: S,B, A, C,D,E,F(iii)因ni工n，考慮S,B，因?yàn)镾b =B S,BBb =DC,D,E,F故 S 和 B 可區(qū)分，于是便得到下一分劃n： S, B, A, C,D,E,F(iv )又因n 2工n，再考慮C,D,E,F,因?yàn)镃a =Fa =C,Cb