1.P36第6题：令文法G6为N→D|NDD→0|1|2|3|4|5|6|7|8|9(1)G6的语言L(G6)是什么?(2)给出句子0127、34和568的最左推导和最右推导解：(1)G6的语言L(G6)为：L(G6)={x|x为可带前导0的正整数}或L(G6)={x|x为数字串}+或L(G6)={(0|1|2|3|4|5|6|7|8|9)}(2)分析：最左推导：任何一步α=>β都是对α中的最左非终结符进行替换最右推导：任何一步α=>β都是对α中的最右非终结符进行替换句子0127、34和568的最左推导如下：N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127N=>ND=>DD=>3D=>34N=>ND=>NDD=>DDD=>5DD=>56D=>568句子0127、34和568的最右推导如下：N=>ND=>N7=>ND7=>N27=>ND27=>N127=>D127=>0127N=>ND=>N4=>D4=>34N=>ND=>N8=>ND8=>N68=>D68=>5682.P36第7题：写一个文法，使其语言是奇数集，且每个奇数不以0开头解：如：G[S]=<VT,VN,S,P>，VT={0,1,2,3,4,5,6,7,8,9}；VN={S,A,B,C,D}其中P为:S→AB|BA→AC|DB→1|3|5|7|9C→0|DD→1|2|3|4|5|6|7|8|93.P36第8题：令文法为：E→T|E+T|E-TT→F|T*F|T/FF→(E)|i(1)给出i+i*i、i*(i+i)的最左推导和最右推导(2)给出i+i+i、i+i*i和i-i-i的语法树1解：(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)(2)i+i+i、i+i*i和i-i-i的语法树分别见图3-1,3-2和3-3图3-1图3-2图3-34.P36第9题：证明下面的文法是二义的：S→iSeS|iS|i解：分析：要证明一个文法具有二义性，方法有两个：①找到该文法的某个句子，对该句子存在两个不同的最左(右)推导例如：存在句子iiiei，它存在两个不同的最左推导S=>iSeS=>iiSeS=>iiieS=>iiieiS=>iS=>iiSeS=>iiieS=>iiiei②找到该文法的某个句子，它对应两棵不同的语法树例如：存在句子iiiei，它对应了两棵不同的语法树由于该文法的句子iiiei存在两个不同的最左推导，因此该文法是二义文法25.P36第11题：给出下面语言的相应文法nniL1={abc|n≥1,i≥0}innL2={abc|n≥1,i≥0}nnmmL3={abab|n,m≥0}nmmnL4={1010|n,m≥0}解：G1[S]:S→ABA→aAb|abB→Bc|εG2[S]:S→ABA→Aa|εB→bBc|bcG3[S]:S→ABA→aAb|εB→aBb|εG4[A]:A→1A0|0B1|εB→0B1|ε6.P64第8题：给出下面正规表达式：(1)以01结尾的二进制数串(2)能被5整除的十进制整数*解：(1)(0|1)01**(2)((1|2|…|9)(0|1|2|…|9))(0|5)7.P64第7题：构造下列正规式相应的DFA*(1)1(0|1)101****(2)0101010*解：(1)1(0|1)101，先构造NFA3确定化：0101{1}-{2,3,4}1-2{2,3,4}{3,4}{3,4,5}234{3,4}{3,4}{3,4,5}334{3,4,5}{3,4,6}{3,4,5}454{3,4,6}{3,4}{3,4,5,7}536{3,4,5,7}{3,4,6}{3,4,5}654DFA的状态转换图如下：附：最小化的DFA：****(2)0101010，先构造NFA确定化：4