搜索
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题：给出下面语言的相应文法L1={anbnci|n≥1,i≥0}L2={aibncn|n≥1,i≥0}L3={anbnambm|n,m≥0}L4={1n0m1m0n|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)0*10*10*10*解：(1)1(0|1)*101，先构造NFA3确定化：01{1}-{2,3,4}{2,3,4}{3,4}{3,4,5}{3,4}{3,4}{3,4,5}{3,4,5}{3,4,6}{3,4,5}{3,4,6}{3,4}{3,4,5,7}{3,4,5,7}{3,4,6}{3,4,5}011-2234334454536654DFA的状态转换图如下：附：昀小化的DFA：(2)0*10*10*10*，先构造NFA确定化：401{1,2,3}{2,3}{4,5,6}{2,3}{2,3}{4,5,6}{4,5,6}{5,6}{7,8,9}{5,6}{5,6}{7,8,9}{7,8,9}{8,9}{10,11,12}{8,9}{8,9}{10,11,12}{10,11,12}{11,12}-{11,12}{11,12}-0112322334544556766778-88-DFA的状态转换图如下：附：昀小化的DFA如下：8.P64第12题：将图3.18的(a)确定化，将(b)昀少化（1）将图3.18的(a)确定化解：ab{0}{0,1}{1}{0,1}{0,1}1}{1}{0}-ab01211220-确定化之前确定化之后另附昀少化：将终态集和非终态集作为基本分划：{0,1}、{2}5考虑{0,1}：由于{0,1}a={1,1}{0,1}{0,1}⊂⊂b={2,2}{2}因此{0,1}不可再分；昀终分划为：{0,1}、{2}分别用状态0、2代表上述集合，且包含原终态的子集对应的状态为新终态（2）将图3.18的(b)昀少化解：将终态集和非终态集作为基本分划：{0,1}{2,3,4,5}考虑{0,1}：由于{0,1}a={1}{0,1}{0,1}⊂b={2,4}⊂{2,3,4,5}因此{0,1}不可再分；考虑{2,3,4,5}：{2,3,4,5}a={1,3,0,5}落在当前分划的两个字集中因此将{2,3,4,5}一分为二：由于{2,4}a={0,1}{3,5}a={3,5}{2,4}b={3,5}{3,5}b={2,4}因此将{2,3,4,5}划分为{2,4}和{3,5}。当前分划为{0,1}、{2,4}、{3,5}再分别考虑上述三个子集，均不可再分。昀终分划为：{0,1}、{2,4}、{3,5}分别用状态1、2、3代表上述集合，且包含原终态的子集对应的状态为新终态昀小化的DFA如下：9.P65第14题构造一个DFA，它接受Σ={0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。解答：（0|10）*NFA如下：状态转换表如下：6II0I1{1,2,4}{2,4}{3}{2,4}{2,4}{3}{3}{2,4}-0112322332-DFA如下：化简：(1)基本分划：{1,2}，{3}(2){1,2}0={2,2}{1,2}⊂{1,2}1={3,3}{3}无需再分⊂(3)昀后分划为：{1,2}，{3}10.P64第15题：给定右线性文法G:S→0S|1S|1A|0BA→1C|1B→0C|0C→0C|1C|0|1求出一个与G等价的左线性文法解答：右线性文法=有限自动机7有限自动机=左线性正规文法G[F]：F→A1|B0|C0|C1A→A1B→B0C→C0|C1S→S0|S1|0|111.P81第1题：考虑下面文法G1:S→a||(T)∧T→T,S|S(1)消去G1的左递归(2)经改写后的文法是否是LL(1)的？给出它的预测分析表解：(1)S→a||(T)∧T→ST′T′→,ST′|ε(2)改写后的文法是LL(1)的，因为：1）改写后的文法不含左递归2）对于产生式S→a||(T)∧：FIRST(a)={a}FIRST()={}∧∧FIRST((T))={（}FIRST(a)∩FIRST()∩FIRST((T))=Φ∧；对于产生式T′→,ST′|ε：FIRST(,ST′)={，}FIRST(ε)={ε}FIRST(,ST′)∩FIRST(ε)=Φ83）对文法中的非终结符T′，其某个候选首符集包含ε，但FIRST(T′)={,，ε}FOLLOW(T′)={）}FIRST(T′)∩FOLLOW(T′)==Φ因此，改写后的文法是LL(1)的。FIRST(S)={a，∧，(}FOLLOW(S)={#}FIRST(T)={a，∧，(}FOLLOW(T)={）}FIRST(T′)={,，ε}FOLLOW(T′)={）}预测分析表：a∧(),#SS→aS→∧S→(T)TT→ST′T→ST′T→ST′T′T′→εT′→,ST′12.P81第2题：对下面的文法G:E→TE′E′→+E|εT→FT′T′→T|εF→PF′F′→*F′|εP→(E)|a|b|∧(1)计算该文法每个非终结符的FIRST和FOLLOW(2)证明该文法是LL(1)的(3)构造它的预测分析表解：(1)文法G的每个非终结符的FIRST为：FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,}∧FIRST(E′)={+,ε}FIRST(T′)={(,a,b,,ε}∧FIRST(F′)={*,ε}文法G的每个非终结符的FOLLOW为：FOLLOW(E)=FOLLOW(E′)={#,)}FOLLOW(T)=FOLLOW(T′)={+,#,)}FOLLOW(F)=FOLLOW(F′)={(,a,b,,#,+,)}∧FOLLOW(P)={*,(,a,b,,#,+,)}∧(2)证明该文法是LL(1)文法分析：判定一个文法是LL(1)文法的充要条件是：对形如：A→α1|α2|…|αn的产生式，有下述条件成立：9①FIRST(α1)∩FIRST(α2)∩…∩FIRST(αn)=φ②若存在αiε，i=1,2,…,n，则有FIRST(A)∩FOLLOW(A)=φ该文法形如A→α1|α2|…|αn的产生式有：E′→+E|εT′→T|εF′→*F′|εP→(E)|a|b|∧分别考虑上述产生式：产生式P→(E)|a|b|∧显然满足①且不存在②的可能其它产生式存在αiε：E′→+E|ε：FIRST(+E)∩FIRST(ε)={+}∩{ε}=φFIRST(E′)∩FOLLOW(E′)={+,ε}∩{#,)}=φT′→T|ε：FIRST(T)∩FIRST(ε)={(,a,b,}∩{ε}=φ∧FIRST(T′)∩FOLLOW(T′)={(,a,b,,ε}∩{+,),#}=φ∧F′→*F′|ε：FIRST(*F′)∩FIRST(ε)={*}∩{ε}=φFIRST(F′)∩FOLLOW(F′)={*,ε}∩{(,a,b,,#,+,)}=φ∧因此该文法是LL(1)文法(3)构造预测分析表FIRST(E)={(,a,b,}∧FOLLOW(E)={),#}FIRST(E′)={+,ε}FOLLOW(E′)={),#}FIRST(T)={(,a,b,}∧FOLLOW(T)={+,),#}FIRST(T′)={(,a,b,,ε}∧FOLLOW(T′)={+,),#}FIRST(F)={(,a,b,}∧FOLLOW(F)={(,a,b,,+,),#}∧FIRST(F′)={*,ε}FOLLOW(F′)={(,a,b,,+,),#}∧FIRST(P)={(,a,b,}∧FOLLOW(P)={*,(,a,b,,+,),#}∧+*()ab∧#EE→TE′E→TE′E→TE′E→TE′E′E′→+EE′→εE′→εTT→FT′T→FT′T→FT′T→FT′T′T′→εT′→TT′→εT′→TT′→TT′→TT′→εFF→PF′F→PF′F→PF′F→PF′F′F′→εF′→*F′F′→εF′→εF′→εF′→εF′→εF′→εPP→(E)P→aP→bP→∧1013.P133第1题：令文法G1为：E→E+T|TT→T*F|FF→(E)|i证明E+T*F是它的一个句型，指出该句型的所有短语，直接短语和句柄解：1)E+T*F是一个句型，因为存在从文法开始符E到E+T*F的一个推导：E=E+T=E+T*F2)根据该句型对应的语法树为：短语：T*FE+T*F直接短语：T*F句柄：T*F14.P133第2题：考