资源描述：
《编译原理(清华大学第2版)课后习题答案》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第三章N=>D=>{0,1,2,3,4,5,6,7,8,9}N=>ND=>NDDL={a
2、a(0
3、1
4、3..
5、9)n且n>=1}(0
6、1
7、3..
8、9)n且n>=1{ab,}anbnn>=1第6题.(1)<表达式>=><项>=><因子>=>i(2)<表达式>=><项>=><因子>=>(<表达式>)=>(<项>)=>(<因子>)=>(i)(3)<表达式>=><项>=><项>*<因子>=><因子>*<因子>=i*i(4)<表达式>=><表达式>+<项>=><项>+<项>=><项>*<因子>+<项>=><因子>*<因子>+<项>=><因子>*
9、<因子>+<因子>=i*i+i(5)<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<项>=i+<项>=>i+<因子>=>i+(<表达式>)=>i+(<表达式>+<项>)=>i+(<因子>+<因子>)=>i+(i+i)(6)<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<项>=>i+<项>=>i+<项>*<因子>=>i+<因子>*<因子>=i+i*i第7题<表达式><表达式><运算符><表达式><表达式><运算符><表达式>*ii+i1<表达式><表达式><运算符><表达式>i+<表达式><运算符><
10、表达式>i*i第9题语法树sss*ss+aaa推导:S=>SS*=>SS+S*=>aa+a*11.推导:E=>E+T=>E+T*F语法树:EE+TT*F短语:T*FE+T*F直接短语:T*F句柄:T*F12．2短语：直接短语：句柄：13.(1)最左推导：S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa最右推导：S=>ABS=>ABA
11、a=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>a1b1b2a2a3(2)文法：SABSSAaSεAaBb(3)短语：a1,b1,b2,a2,,bb,aa,abbaa,直接短语：a1,b1,b2,a2,,句柄：a114(1)SABAaAb
12、εBaBb
13、ε(2)S1S0SAA0A1
14、ε第四章1.1.构造下列正规式相应的DFA(1)1(0
15、1)*101NFA1101012340,1(2)1(1010*
16、1(010)*1)*0NFA3010001ε1000411000102(3)NFAb2(4)NFAaab2
17、0a14bbεεbab01563εεa,b3ab42.解：构造DFA矩阵表示01{X}0{Z}{X}{Z}*{X,Z}{Y}{X,Z}*{X,Z}{X,Y}{Y}{X,Y}4{X,Y}{X,Y,Z}{X}{X,Y,Z}*{X,Y,Z}{X,Y}其中0表示初态，*表示终态用0，1，2，3，4，5分别代替{X}{Z}{X,Z}{Y}{X,Y}{X,Y,Z}得DFA状态图为：131100000501104213．解：构造DFA矩阵表示构造DFA的矩阵表示01{S}0{V,Q}{Q,U}{V,Q}{Z,V}{Q,U}{Q,U}{V}{Q,U,
18、Z}{Z,V}*{Z}{Z}{V}{Z}{Q,U,Z}*{V,Z}{Q,U,Z}{Z}{Z}{Z}其中0表示初态，*表示终态替换后的矩阵0100121322453*66465*35666构造DFA状态转换图（略）4．（1）解构造状态转换矩阵：5ab{0}0*{0,1}{1}{0,1}*{0,1}{1}{1}{0}转换为ab0*121*1220{2，3}{0，1}{2，3}a={0,3}{2},{3},{0,1}{0,1}a={1,1}{0,1}b={2,2}（2）解：首先把M的状态分为两组：终态组{0}，和非终态组{1，2，3，4,5
19、}此时G=({0},{1,2,3,4,5}){1,2,3,4,5}={1,3,0,5}a{1,2,3,4,5}={4,3,2,5}b由于{4}a={0}{1,2,3,5}a={1,3,5}因此应将{1,2,3,4,5}划分为{4},{1,2,3,5}G=({0}{4}{1,2,3,5}){1,2,3,5}a={1,3,5}{1,2,3,5}b={4,3,2}因为{1,5}b={4}{23}b={2,3}所以应将{1,2,3,5}划分为{1,5}{2,3}G=({0}{1,5}{2,3}{4}){1,5}={1,5}{1,5}b={4}
20、所以{1,5}不用再划分a{2,3}={1,3}{2,3}b={3,2}a因为{2}a={1}{3}a={3}所以{2,3}应划分为{2}{3}所以化简后为G＝（{0},{2},{3},{4},{1,5}）7.去除多余产
