第二章高级语言及其语法描述6．（1）L（G6）={0,1,2,......,9}+（2）最左推导：N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127N=>ND=>DD=>3D=>34N=>ND=>NDD=>DDD=>5DD=>56D=>568最右推导：N=>ND=>N7=>ND7=>N27=>ND27=>N127=>D127=>0127N=>ND=>N4=>D4=>34N=>ND=>N8=>ND8=>N68=>D68=>5687．【答案】Ｇ：S→ABC|AC|CA→1|2|3|4|5|6|7|8|9B→BB|0|1|2|3|4|5|6|7|8|9C→1|3|5|7|98．（1）最左推导：E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*iE=>T=>T*F=>F*F=>i*F=>i*(E)=>i*(E+T)=>i*(T+T)=>i*(F+T)=>i*(i+T)=>i*(i+F)=>i*(i+i)最右推导：E=>E+T=>E+T*F=>E+T*i=>E+F*i=>E+i*i=>T+i*i=>F+i*i=>i+i*iE=>T=>T*F=>T*(E)=>T*(E+T)=>T*(E+F)=>T*(E+i)=>T*(T+i)=>T*(F+i)=>T*(i+i)=>F*(i+i)=>i*(i+i)E-TTFiEE-TFiFiE+TTFiEE+TFiFiE+TFiET*FiFiT(2)9．证明：该文法存在一个句子iiiei有两棵不同语法分析树，如下所示，因此该文法是二义的。SSeiSiSSiiSeiSiSiSiS→TS|TT→(S)|()10.【答案】无二义文法为：11.【答案】G1:S→ABA→aAb|abB→cB|εG2:S→ABA→aA|εB→bBc|bcG4:S→1S0|AA→0A1|εG3:S→AAA→aAb|ε第3章词法分析7．构造下列正规式相应的DFA：(1)1(0|1)*101解：（1）构造NFA：0X152Y0,113411（2）确定化：构造状态转换矩阵如下：重命名：II0I1{X}-{1,5,2}{1,5,2}{5,2}{5,3,2}{5,2}{5,2}{5,3,2}{5,3,2}{5,4,2}{5,3,2}{5,4,2}{5,2}{5,Y,3,2}{5,Y,3,2}{5,4,2}{5,3,2}S010-1123223343425543(3)化简(4)化简之后的状态表分组{0,1,2,3,4}{5}S010-1112232314432考察{0,1,2,3,4}0={2,4}{0,1,2,3,4}1={1,3,5}∴分化为：{0,1,2,3}、{4}、{5}再考察：{0,1,2,3}0={2,4}∴分化为：{0,1,2,}、{3}、{4}、{5}再考察：{0,1,2}0={2}{0,1,2}1={1,3}∴分化为：{0}、{1,2,}、{3}、{4}、{5}(5)画出状态转换图：01210130104101(3)0*10*10*10*解：（1）构造NFA：11X712Y8349561010000（2）确定化：构造状态转换矩阵如下：重命名：II0I1{X,7,1}{7,1}{2,8,3}{7,1}{7,1}{2,8,3}{2,8,3}{8,3}{4,9,5}{8,3}{8,3}{4,9,5}{4,9,5}{9,5}{6,10,Y}{9,5}{9,5}{6,10,Y}{6,10,Y}{10,Y}--{10,Y}{10,Y}--S0101211223433445655667-77-(3)化简如上表所示：{0,1}、{2,3}、{4,5}、{6,7}化简后的状态表为：S0100111222333-（4）最简DFA状态转换图012311100008．（1）（0|1）*01（2）∑={0，1，2，3，4，5，6，7，8，9}((1|2|3|4|5|6|7|8|9）∑*(0|5))|（0|5）（3）1*0((01*0)︱1)*︱0*1((10*1)︱0)*（4）a*b*c*......z*(5)(x0︱)(x1︱)(x2︱)......(x9︱)∑={0,1,.....,