編譯原理第三版第三章習(xí)題與答案

.第3章習(xí)題3-1試構(gòu)造一右線性文法，使得它與如下的文法等價(jià)S→ABA→UTU→aU|aD→bT|bB→cB|c并根據(jù)所得的右線性文法，構(gòu)造出相應(yīng)的狀態(tài)轉(zhuǎn)換圖。3-2對于如題圖3-2所示的狀態(tài)轉(zhuǎn)換圖0100DB0110ACF01E1題圖3-2(1)寫出相應(yīng)的右線性文法；(2)指出它接受的最短輸入串；(3)任意列出它接受的另外4個(gè)輸入串；(4)任意列出它拒絕接受的4個(gè)輸入串。3-3對于如下的狀態(tài)轉(zhuǎn)換矩陣：..abSBBaABBbBABSABASABAB(ⅰ)初態(tài):S終態(tài):B(ⅲ)初態(tài):S終態(tài):BaACBCbBACCaACBCbSBCCSABCSABC(ⅱ)初態(tài):S終態(tài):A,C(ⅳ)初態(tài):S終態(tài):C題圖3-3(1)分別畫出相應(yīng)的狀態(tài)轉(zhuǎn)換圖；(2)寫出相應(yīng)的3型文法；(3)用自然語言描述它們所識別的輸入串的特征。3-4將如下的NFA確定化和最小化：..abaabSAB(1)baaSACBaa(2)abSABb(3)baaBACa,ba(4)題圖3-43-5將如題圖3-5所示的具有ε動作的NFA確定化。..abSABCεεc(1)bSRaaZabεXbbUYa(2)題圖3-5具有ε動作的NFA3-6設(shè)有文法G[S]：S→aAA→aA|bBB→bB|cC|cC→cC|c試用正規(guī)式描述它所產(chǎn)生的語言。3-7分別構(gòu)造與如下正規(guī)式相應(yīng)的NFA。(1)((0*|1)(1*0))*(2)b|a(aa*b)*b3-8構(gòu)造與正規(guī)式(a|b)*(aa|bb)(a|b)*相應(yīng)的DFA。..第3章習(xí)題答案3-1解：根據(jù)文法知其產(chǎn)生的語言是:L[G]={ambnci|m,n,i≧1}可以構(gòu)造與原文法等價(jià)的右線性文法:S→aAA→aA|bBB→bB|cC|cC→cC|c其狀態(tài)轉(zhuǎn)換圖如下:3-2解:(1)其對應(yīng)的右線性文法是G[A]:A→0DD→0B|1CB→0A|1CE→0B|1CC→0A|1F|1F→1A|0E|0(2)最短輸入串為011(3)任意接受的四個(gè)輸入串為：0110,0011,000011,00110(4)任意拒絕接受的輸入串為：0111，1011，1100，10013-3解:(1)相應(yīng)的狀態(tài)轉(zhuǎn)換圖為：..aba,babSAB與(ⅰ)相應(yīng)的狀態(tài)轉(zhuǎn)換圖ba,baaSABCbba與(ⅱ)相應(yīng)的狀態(tài)轉(zhuǎn)換圖ba,baaSABb與(ⅲ)相應(yīng)的狀態(tài)轉(zhuǎn)換圖ba,baaSABCbba與(ⅳ)相應(yīng)的狀態(tài)轉(zhuǎn)換圖答案圖3-3(2)相應(yīng)的3型文法為：(ⅰ)S→aA|bSA→aA|bB|bB→aB|bB|a|b..(ⅱ)S→aA|bB|aA→bA|aC|a|bB→aB|bC|bB→aB|bB|a|bB→aB|bC|bC→aC|bC|a|b(ⅲ)S→aA|bB|b(ⅳ)S→bS|aAA→aB|bA|aA→aC|bB|aC→aC|bC|a|b(3)用自然語言描述的輸入串的特征為：(ⅰ)以任意個(gè)(包括0個(gè))b開頭，中間有任意個(gè)（大于1）a，跟一個(gè)b，還可以有一個(gè)由a,b組成的任意字符串。(ⅱ)以a打頭，中間有任意個(gè)（包括0個(gè)）b,再跟a,最后由一個(gè)a,b所組成的任意串結(jié)尾；或者以b打頭，中間有任意個(gè)（包括0個(gè)）a,再跟b,最后由一個(gè)a,b所組成的任意串結(jié)尾。(ⅲ)以a打頭，后跟任意個(gè)（包括0個(gè)）b，再跟a，最后由一個(gè)a,b所組成的任意串結(jié)尾；或者以b打頭，由一個(gè)a,b所組成的任意串結(jié)尾。(ⅳ)以任意個(gè)（包括0個(gè)）b開頭,中間跟aa，最后由一個(gè)a,b所組成的任意串結(jié)尾；或者以任意個(gè)（包括0個(gè)）b開頭，中間跟ab后，再接任意個(gè)（包括0個(gè)）a，再接b，最后由一個(gè)a,b所組成的任意串結(jié)尾。3-4解：(1)將NFAM確定化后得DFAM′，其狀態(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組成了DFAM′的終態(tài)集Z′。于是，所構(gòu)造之DFAM′的狀態(tài)轉(zhuǎn)換矩陣和狀態(tài)轉(zhuǎn)換圖如答案圖3-4-(1)之(b)及(c)所示。..aba2244b[S][S,A]1234[S,A][S,A][A,B][A,B][B]33[A,B][B][B]初態(tài):[S]終態(tài):[A,B],[B](a)確定化后的狀態(tài)矩陣初態(tài):1終態(tài):3,4(b)改名后的狀態(tài)矩陣abaaba1234(c)DFAM′的狀態(tài)轉(zhuǎn)換圖答案圖3-4-(1)現(xiàn)將DFAM′最小化：(ⅰ)初始分劃由兩個(gè)子集組成，即π:{1,2},{3,4}0(ⅱ)為得到下一分劃，考察子集{1,2}。因?yàn)閧2}={3}{3,4}b但{1}=b故1和2可區(qū)分，于是便得到下一分劃π:{1},{2},{3,4}1(ⅲ)又因π≠π，再考慮{3,4}，因?yàn)?0{3}={3}{3,4}b而{4}=b故3和4可區(qū)分，從而又得到π:{1},{2},{3},{4}2此時(shí)子集已全部分裂，故最小化的過程宣告結(jié)束，M′即為狀態(tài)數(shù)最小的DFA。..(2)將NFAM確定化后得DFAM′，其狀態(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)所示。aba232b2[S][A]123[A][B,C][B,C][A][A]初態(tài):[S]終態(tài):[B,C]初態(tài):1終態(tài):3(b)改名后的狀態(tài)矩陣(a)確定化后的狀態(tài)矩陣baa123a(c)DFAM′的狀態(tài)轉(zhuǎn)換圖答案圖3-4-(2)現(xiàn)將DFAM′最小化：(ⅰ)初始分劃由兩個(gè)子集組成，即π:{1,2},{3}0(ⅱ)為得到下一分劃，考察子集{1,2}。因?yàn)閧2}={2}{1,2}b但{1}=b故1和2可區(qū)分，于是便得到下一分劃π:{1},{2},{3}1此時(shí)子集已全部分裂，故最小化的過程宣告結(jié)束，M′即為狀態(tài)數(shù)最小的DFA。..(3)將NFAM確定化后得DFAM′，其狀態(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)所示。aba2b3[S][A][A]123[S,B][S,B][A]2初態(tài):[S]終態(tài):[S,B]初態(tài):1終態(tài):3(b)改名后的狀態(tài)矩陣(a)確定化后的狀