第3章习题

文法和语言的基本知识习题课1.设有文法G[A]：Aa|b|e|Aa|Ae|A0|A1(1)试问VT和VN是由哪些符号组成？(2)下列符号串a,ab0,a0e01,0a,11,eee是否为该文法的句子？解答:(1)VT={a,b,e,0,1}VN={A}(2)A→aA→A1→A01→Ae01→A0e01→a0e01A→Ae→Aee→eee所以a,a0e01,eee是该文法的句子。2.设有文法G[N]：ND|NDD0|1|2|3|4|5|6|7|8|9(1)G[N]定义的语言是什么？(2)给出句子0123和268的最左推导和最右推导。解答:(1)N→ND→NDD→D…D,所以L(G[N])={а|а为可带前导0的正整数}(2)N→ND→NDD→NDDD→DDDD→0DDD→01DD→012D→0123N→ND→N3→ND3→N23→ND23→N123→D123→0123N→ND→NDD→DDD→2DD→26D→268N→ND→N8→ND8→N68→D68→2683.给出下面语言相应的文法。L1={ambn|m,n1}解答:当m=1,n=1时,L1={ab}当m=1,n=2时,L1={abb}当m=1,n=3时,L1={abbb}当m=2,n=3时,L1={aabbb}…所以，定义语言L1的文法：G={{A，B}，{a,b},{A→a|aA|AB,B→b|bB},A}(错）文法G1:S→ABA→aA|aB→bB|b（对）L2={anbnci|n1,i0}解答:当n=1,i=0时,L={ab}当n=1,i=1时,L={abc}当n=2,i=0时,L={aabb}当n=3,i=1时,L={aaabbbc}…所以，定义语言L2的文法：G={{A,B},{a,b,c},{A→ab|aAbB,B→c|ε},A}(错）文法G2：S→Sc|AA→ab|aAb（对）L3={anbncmdm|n1,m1}解答:当m=1,n=1时,L={abcd}当m=2,n=1时,L={abccdd}当m=1,n=2时,L={aabbcd}…所以，定义语言L3的文法：G={{A,B},{a,b,c,d},{A→ab|aAb|AB,B→cd|cBd},A}(错）文法G3:S→ABA→aAb|abB→cBd|cd（对）L4={0n|n0}解答:当n=0时，为ε当n=1时,为0(错）所以，定义语言L4的文法：G={{A},{0},{A→0A∣0∣ε},A}（对）文法G4：A→0A|ε（对）L5={a2n+1|n0}解答:当n=0时,L5={a}当n=1时,L5={a3}当n=2时,,L5={a5}…所以，定义语言L5的文法：G={{A},{a},{A→a∣aAa},A}（对）文法G5:A→aAa|a（对）L6={1n0m1m0n|n,m0}解答:当n=m=0时,L6={εεεε}当n=m=1时,L6={1010}当n=1,m=0时,L6={1εε0}当n=0,m=1时,L6={εε01}…所以，定义语言L6的文法：G={{A},{0,1},{A→ε|0A1|1A0},A}(错）文法G6：S→ε|1S0|0A1A→ε|0A1（对）4.写一个文法，使其语言是奇数的集合，且每个奇数不以0开头。解答:因为奇数要满足最后一位为1、3、5、7、9，且第一位不为零，所以该文法为：N→1|3|5|7|9|BNB→1|2|3|4|5|6|7|8|9|B05.证明下面的文法是二义性的。S→iSeS|iS|i证明:句子iiiei有两个不同的最左推导，对应两棵不同的语法树，最左推导一：最左推导二：S=iS=iiSeSS=iSeS=iiSeS=iiieS=iiiei=iiieS=iiieiSS/＼/||＼iSiSeS/||＼/＼\iSeSiSi||||iiii所以该文法是二义性的。6.设有文法G[E]：E→E+T|E-T|TT→T*F|T/F|FF→（E）|i试证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。证明：因为E=E+T=E+T*F，所以E+T*F是文法G[E]的句型。E/|\E+T/|\T*F由语法树知：E+T*F为句型的相对于E的短语；T*F为句型的相对于T的短语，且为直接短语和句柄。7.下面文法生成的语言是什么？G1：S→ABA→aA|εB→bc|bBc解答:L(G1（N）)={bc,abc,aabc,abbcc…}即L(G1（N）)={ambncn,m=0,n=1}G2：S→aA|aA→aS解答:因为S=aS=aA=aaS=aaaS=aA=aaA=aaaS=aaaaA=aaaaa…所以L(G2[S])={a2n+1|n≥0}8.试证明文法G[表达式]是二义性文法。表达式→i|表达式运算符表达式运算符→+|-|*|/证明：文法句子i+i*i有下面两棵不同的语法树，所以该文法是二义性的。表达式/|\表达式运算符表达式/|\||表达式运算符表达式*i/|\i+i表达式/|\表达式运算符表达式||/|\i+表达式运算符表达式|||i*i9.设有文法T→T*F|FF→F↑P|PP→(T)|i试给出句型T*P↑(T*F)的语法树，并指出这个句型的所有短语、直接短语和句柄。解答:T=T*F=T*F↑P=T*P↑P=T*P↑(T)=T*P↑(T*F)TT*P↑(T*F)是句型相对于T的短语；/|\P↑(T*F)是句型相对于F的短语；T*F(T*F)是句型相对于P的短语；/|\T*F是句型相对于T的短语，且为直接短语；F↑PP是句型相对于F的短语,且为直接短语和句柄。|/|\P(T)/|\T*F10.文法G[A]=（{A}，{a,b},{A→bA|a},A)所生成的语言是什么？解答:因为A=aA=bA=baA=bA=bbA=bba…所以生成的语言为L(G[A])={bna|n≥0}。11.已知文法G[S]：S→（AS）|（b)A→(SaA)|（a)试找出符号串（a)和（A((SaA)(b)))的短语、直接短语和句柄。解答:S=((AS)=((aA)S)≠(a),所以符号串（a）不是文法的句型，因此它没有短语，直接短语和句柄。S=(AS)=(A(AS))=(A(A(b)))=(A((SaA)(b))),所以符号串(A((SaA)(b)))是文法的句型。它的语法树是：S(A((SaA)(b)))是句型相对于S的短语;/||\((SaA)(b))是句型相对于S的短语;(AS)(SaA)是句型相对于A的短语,且为直接短语，/|\\和句柄。(AS)（b)是句型相对于S的短语,且为直接短语。/|||\\\\(SaA)(b)12.解释下列术语和概念（1）字母表：元素的非空有穷集合。（2）上下文无关文法：若文法G=（VN,，VT，P，S）中的每一条规则的形式为A→β，其中A∈VN,β∈(VNUVT)*,则称G是2型文法，即上下文无关文法。（3）正规文法：若文法G=（VN，VT，P，S）中的每一条规则的形式为A→αB或A→α，其中，A，B∈VN，α∈VT*，则称G是右线性文法，即正规文法。（4）句柄：一个句型的最左直接短语称为该句型的句柄。（5）规范推导：最右推导也称为规范推导。（6）文法二义性：如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义性的。