资源描述：
《编译原理(清华大学-第2版)课后习题答案.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
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题36第9题语法树推导:S=>SS*=>SS+S*=>aa+a*11.推导:E=>E+T=>E+T*F语法树:短语:T*FE+T*F直接短
10、语:T*F句柄:T*F12．36短语：直接短语：句柄：13.(1)最左推导：S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa最右推导：S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>a1b1b2a2a3(2)文法：SàABSSàAaSàεAàaBàb(3)短语：a1,b1,b2,a2,,bb,aa,abbaa,直接短语：a
11、1,b1,b2,a2,,句柄：a114(1)SàABAàaAb
12、εBàaBb
13、ε(2)Sà1S0SàAAà0A1
14、ε第四章1.1.构造下列正规式相应的DFA(1)1(0
15、1)*101NFA(2)1(1010*
16、1(010)*1)*0NFA36(3)NFA(4)NFA2.解：构造DFA矩阵表示01{X}0{Z}{X}{Z}*{X,Z}{Y}{X,Z}*{X,Z}{X,Y}{Y}{X,Y}36{X,Y}{X,Y,Z}{X}{X,Y,Z}*{X,Y,Z}{X,Y}其中0表示初态，*表示终态用0，1，2，3，4，5分别代替{X}{Z}{
17、X,Z}{Y}{X,Y}{X,Y,Z}得DFA状态图为：3．解：构造DFA矩阵表示构造DFA的矩阵表示01{S}0{V,Q}{Q,U}{V,Q}{Z,V}{Q,U}{Q,U}{V}{Q,U,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）解构造状态转换矩阵：36ab{0}0*{0,1}{1}{0,1}*{0,1}{1}{1}{0}转换为ab0*121*122
18、0{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}此时G=({0},{1,2,3,4,5}){1,2,3,4,5}a={1,3,0,5}{1,2,3,4,5}b={4,3,2,5}由于{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
19、,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}a={1,5}{1,5}b={4}所以{1,5}不用再划分{2,3}a={1,3}{2,3}b={3,2}因为{2}a={1}{3}a={3}所以{2,3}应划分为{2}{3}所以化简后为G＝（{0},{2},{3},{4},{1,5}）7.去除多余产生式后，构造NFA如下36确定化，构造DFA矩阵abSAQAAB,ZB,ZQDQQD,ZDABD,ZADBQD
20、变换为ab00131122*343354165*14634化简：G={(0,1,3,4,6),(2,5)}{0,1,3,4,6}a={1,3}{0,1,3,4,6}b={2,3,4,5,6}所以将{0,1,3,4,6}划分为{0,4,6}{1,3}G={(0,4
