蔣立源編譯原理第三版第三章習題與答案

1、第 3 章 習題3-1 試構(gòu)造一右線性文法，使得它與如下的文法等價4AB A f UT U faU|a D fbT|b B fcB|c并根據(jù)所得的右線性文法，構(gòu)造出相應(yīng)的狀態(tài)轉(zhuǎn)換圖。3-2對于如題圖 3-2 所示的狀態(tài)轉(zhuǎn)換圖(1)寫出相應(yīng)的右線性文法；(2)指出它接受的最短輸入串；(3)任意列出它接受的另外 4 個輸入串；(4)任意列出它拒絕接受的 4 個輸入串。3-3對于如下的狀態(tài)轉(zhuǎn)換矩陣：(1)分別畫出相應(yīng)的狀態(tài)轉(zhuǎn)換圖；(2)寫出相應(yīng)的 3 型文法；(3)用自然語言描述它們所識別的輸入串的特征。3-4將如下的NFA確定化和最小化:3-5將如題圖3-5所示的具有£動作的 NFA確定

2、化。題圖 3-5 具有£動作的 NFA3-6設(shè)有文法 GS :4 aA L aA|bB4 bB|cC|cC cC|c試用正規(guī)式描述它所產(chǎn)生的語言。3-7分別構(gòu)造與如下正規(guī)式相應(yīng)的NFA(1) (0 |1)(1 0)DFA b|a(aa *b)*b3-8構(gòu)造與正規(guī)式(a|b) *(aa|bb)(a|b)*相應(yīng)的第3章習題答案3-1 解：根據(jù)文法知其產(chǎn)生的語言是LG=a m3nci| m,n,i 仝 1可以構(gòu)造與原文法等價的右線性文法A aA|bB4 bB|cC|cC cC|c其狀態(tài)轉(zhuǎn)換圖如下：c3-2 解:(1)其對應(yīng)的右線性文法是 GA:0A|1F|14 0A|1CDf0B|1CEf

3、0B|1CFf 1A|0E|0(2)最短輸入串為 O11(3)任意接受的四個輸入串為：0110,0011,000011,00110(4)任意拒絕接受的輸入串為：0111，1011，1100，10013-3解:(1)相應(yīng)的狀態(tài)轉(zhuǎn)換圖為：(2)相應(yīng)的 3 型文法為：(i ) S f aA|bSAfaA|bB| bBf aB|bB|a|b(ii) S f aA|bB|AfbA|aC| a|bBfaB|bC|bCf aC|bC|a|b(iii) S f aA|bB|AfaB|bA| aBfaB|bB|a|b(iv) S f bS|aAAfaC|bB| aBfaB|bC| bCf aC|bC|a|b（3

4、） 用自然語言描述的輸入串的特征為：（i ）以任意個（包括0個）b開頭，中間有任意個（大于1） a,跟一個b,還可以有一個由 a,b 組成的任意字符串。（ii）以a打頭，中間有任意個（包括0個）b,再跟a,最后由一個a,b所組成的任意串結(jié)尾；或者以b打頭，中間有任意個（包括0個）a,再跟b,最后由一個a,b 所組成的任意串結(jié)尾。（iii）以a打頭，后跟任意個（包括0個）b ,再跟a,最后由一個a,b所組成的任意串結(jié)尾；或者以 b 打頭,由一個 a,b 所組成的任意串結(jié)尾。（v）以任意個（包括0個）b開頭，中間跟aa,最后由一個a,b所組成的任意串結(jié)尾；或者以任意個（包括 0個）b開頭，中間跟a

5、b后，再接任意個（包括 0個）a,再接b,最后由一個a,b所組成的任意串結(jié)尾。3-4 解:(1)將NFA M確定化后得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)所示?，F(xiàn)將DFA M最小化:(i )初始分劃由兩個子集組成，即n 0：1,2, 3,4(ii)為得到下一分劃，考察子集1,2 0因為2 b =33,41和2可區(qū)分，于是便得到下一分劃n 1

6、： 1, 2, 3,4(iii)又因n 1工n0，再考慮3,4，因為3 b =33,44故3和4可區(qū)分，從而又得到n 2： 1, 2, 3, 4此時子集已全部分裂，故最小化的過程宣告結(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為DFAM的終態(tài)。于是，所構(gòu)造之 DFAM的狀態(tài)轉(zhuǎn)換矩陣和狀態(tài)轉(zhuǎn)換圖如答案圖3-4-(2)之(b)及(c)所示。現(xiàn)將DFA M最小化:(i )初始分劃由兩個子集組成，即n 0：1,2, 3(ii)為得到下一分劃，

7、考察子集1,2 0因為2 b =21,2但 1故1和2可區(qū)分，于是便得到下一分劃n 1： 1, 2, 3此時子集已全部分裂，故最小化的過程宣告結(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)B,故3為DFAM的終態(tài)。于是，所構(gòu)造之 DFAM的狀態(tài)轉(zhuǎn)換矩陣和狀態(tài)轉(zhuǎn)換圖如答案圖3-4-(3)之(b)及(C)所示。現(xiàn)將DFA M最小化:(i )初始分劃由兩個子集組成，即n 0：1,2, 3(ii)為得到下一分劃，考察子集1,2 0因為2 b =3但 1

8、故1和2可區(qū)分，于是便得到下一分劃n 1： 1, 2, 3此時子集已全部分裂，故最小化的過程宣告結(jié)束，M即為狀態(tài)數(shù)最小的 DFA3-4-(4)之(a)所示,(4)將NFA M確定化后得DFA M，其狀態(tài)轉(zhuǎn)換矩陣如答案圖給各狀態(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)所示。現(xiàn)將DFA M最小化:(i )初始分劃由兩個子集組成，即n 0：1,3, 2,4(ii)為得到下一分劃，考察子集1,3。因為1a=22,4但 3a=

9、11,3故1和3可區(qū)分，于是便得到下一分劃n 1: 1, 3, 2,4(iii)又因n 1工n0,再考慮2,4，因為2 a =4 a =1, 2 b =4b =4所以2和4不可區(qū)分,故子集S,B已不能再分裂。此時n 2 =n 1 ,子集分裂的過程宣告結(jié)束。(iv )現(xiàn)選擇狀態(tài)至4的矢線都引至2,2作為2,4的代表，將狀態(tài)4從狀態(tài)轉(zhuǎn)換圖中刪去，并將原來引這樣，我們就得到了最小化后的DFA M如答案圖3-4- 之(d) 所示。3-5 解:(1)將具有£動作的NFAM確定化后得DFAM'，其狀態(tài)轉(zhuǎn)換矩陣如答案圖3-5-(1)之(a)所示，給各狀態(tài)重新命名，即令:S,B,C=1,A=

10、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)所示。 將具有£動作的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)造之 DFA M的狀態(tài)轉(zhuǎn)換矩陣和狀態(tài)轉(zhuǎn)換圖如答

11、案圖3-5-(2)之(b)及(c)所示。3-6 解:首先將文法寫成方程組:S=aA(1)A=aA+bB(2)B=bB+cC+c(3)C=cC+c(4)將(4) 代入 (3) ，得:B=bB+C由論斷，方程 (4) 的解為 :C=cc將上式代入 (5) ，得:B=bB+c由論斷，得:(5)B=b* c*c將上式代入 (2)，得：A=aA+bbc c由論斷，得：A=a* b*bc*c將上式代入 (1)，得：S=a* ab*bc * c即文法所產(chǎn)生的語言可用正規(guī)式a*ab*bc*c 表示。3-7解：(1)(2)構(gòu)造與正規(guī)式(0* 11)(1 *0)*相應(yīng)的NFA的步驟如答案圖3-7-(1)所示:構(gòu)造

12、與正規(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)的NFAM其構(gòu)造步驟如答案圖 3-8(a)所示:其次，將答案圖3-8(a)所示的具有£動作的 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

13、,D,E和F的組成中均含有 NFA M的終態(tài)態(tài)集Z'。于是，將NFA M確定化后所得DFA M乙故C,D,E和F組成了 DFA M 的終的狀態(tài)轉(zhuǎn)換矩陣和狀態(tài)轉(zhuǎn)換圖如答案(e) 對DFA M最小化后所得的DFA M'的狀態(tài)轉(zhuǎn)換圖圖3-8(c)及(d)所示。答案圖3-8最后，將所得DFA M最小化:(i )初始分劃由兩個子集組成，即n 0：S,A,B, C,D,E,F(ii)為得到下一分劃，考察子集S,A,B。因為S,B a =ASAB但 Aa =CC,D,E,F故S,B和A可區(qū)分，于是便得到下一分劃n 1: S,B, A, C,D,E,F(iii)因n 1工n 0 ,考慮S,B，因為Sb=BS,B但 Bb =DC,D,E,F故S和B可區(qū)分，于是便得到下一分劃n 2: S, B, A, C,D,E,F(iv)又因n 2工n 1 ,再考慮C,D,E,F，因為Ca=Fa=C, C b =Fb =E所以C和F等價；同理可得 D和E等價。又因為Ca =C, D