编译原理习题与答案VIP免费

第二章2.2设有文法G[N]:N->D|NDD->0|1|…|9(1)G[N]定义的语言是什么？(2)请给出句子0123的最左推导和最右推导。NNDNDDNDDDDDDD0DDD01DD012D0123NNDN3ND3N23ND23N123D12301232.5证明下面的文法是二义性的。S→iSeS|iS|i答：对句子iiiei对应两棵不同的语法树第二章SiSSeiSiiSiSSeiSii2.9设有文法G[T]:T→T*F|FF→FîP|PP→(T)|i分析句型T*Pî(T*F)的短语、直接短语和句柄答：句型T*Pî(T*F)的语法树：TTF*()T五棵子树对应五个短语T*Pî(T*F),Pî(T*F),P,(T*F),T*F两层子树(简单子树)的末端结点构成直接短语两棵两层子树对应两个直接短语：P,T*F位于最左边的两层子树的末端结点构成句柄：P第二章PFîPTF*第三章3.1构造正规式1(0|1)*101相应的NFAX1B1C10DYA(0|1)*X1B1C10DYAεEε0|1X1B1C10DYAεEε0,1第三章3.1构造正规式1(0|1)*101相应的NFAX11B10CYA(0|1)*0,1X11B10CYAX1B1C10DYAεEε0,1第三章3.5给出下述文法所对应的正规式。G：S→aAA→bA|aB|bB→aA解：先由产生式得:B=aA将B代入A中得:A=bA|aaA|b=(b|aa)A|b利用规则（A->xA|y）得:A=(b|aa)*b将A代入S中得:S=a(b|aa)*b即为所求正规式3.4给出文法G[S]，构造相应最小的DFA。G：S→aS|bA|bA→aS解：由文法到NFA的转换有两种方法：①由文法到正规式，再由正规式到NFA先由产生式得:A=aS将A代入S中得:S=aS|bA|b=aS|baS|b=(a|ba)S|b利用规则（A->xA|y）得:S=(a|ba)*b文法G对应的正规式为(a|ba)*b，其对应的NFA的状态转换图为：第三章3.4给出文法G[S]，构造相应最小的DFA。G：S→aS|bA|bA→aS解：②由文法直接到NFA文法对应的有自动M=({S,A,T},{a,b},f,S,{T})其对应的状态转换图为：产生式转换函数S→aSf(S,a)=SS→bAf(S,b)=AS→bf(S,b)=TA→aSf(A,a)=S第三章正规式：(a|ba)*bTbSAaba产生式转换函数S→aSf(S,a)=SS→bAf(S,b)=AS→bf(S,b)=TA→aSf(A,a)=S第三章将NFA确定化为DFA如右图所示最小化：此状态图已经为最简了。TbSAaba{S}{S}{A,T}{A,T}{S}IbIaI0101001aba--第三章1.指出与正规式匹配的串。a)(ab|b)*c与后面的那些串匹配？ababbcababcbabcaaabcb)ab*c*(a|b)c与后面的那些串匹配？acacacbbcabbcacabcaccc)(a|b)aa*(ba)*与后面的那些串匹配?babbabaaaaababa第三章2.为下边所描述的串写正规式，字母表是{0,1}.a)以01结尾的所有串b)只包含一个0的所有串c)包含偶数个1但不含0的所有串d)包含偶数个1且含任意数目0的所有串e)包含01子串的所有串f)不包含01子串的所有串(0|1)*011*01*(11)*(0*10*10*)*(0|1)*01(0|1)*1*0*第三章3.请描述下面正规式定义的串.字母表S={x,y}。a)x(x|y)*x必须以x开头和x结尾的串b)x*(yx+)*x*每个y至少有一个x跟在后边的串c)(x|y)*(xx|yy)(x|y)*所有含两个相继的x或两个相继的y的串第三章4.指出哪些串是自动机可接受的xyxyxxyyyyxxyyxyxyxxy第三章5.将下图所示的非确定有限自动机(NFA)变换成等价的确定有限自动机(DFA)。XY1342abaabbabab第三章解:用子集法将NFA确定化，如下图所示。IIaIb{X}{1}{3}{2,3,Y}{3,Y}{1}－{3,4}{3}{2,3,4,Y}{2,3,Y}{2,3,Y}{2,3,Y}{3,4}{3,Y}{3,4,Y}{3,4}{3,4}{2,3,4,Y}{2,3,4,Y}{2,3,4,Y}{2,3,4,Y}{3,4,Y}{3,4,Y}ba01213425－336435557666767重新命名XY1342abaabbabab上图所对应的DFA如下所示。345aabba2bb01a7bb6babaa第三章ba01213425－336435557666767对上图的DFA进行最小化。首先将状态分为非终态集和终态集两部分：{0,1,2,5}和{3,4,6,7}。由终态集可知，对于状态3、6、7，无论输入字符是a还是b的下一状态均为终态集，而状态4在输入字符b的下一状态落入非终态集，故将其化为分{0,1,2,5},{4},{3,6,7}第三章ba01213425－336435557666767第三章对于非终态集，在输入字符a、b后按其下一状态落入的状态集不同而最终划分为{0},{1},{2},{5},{4},{3,6,7}按顺序重新命名为0、1、2、3、4、5，得到最简DFA如下图所示。{0,1,2,5},{4},{3,6,7}ba01213425－336435557666767012ab435aabbbbbaa345aabba2bb01a7bb6babaa6.设有L(G)={a2n+1b2ma2p+1|n≥0,p≥0,m≥1}。(1)给出描述该语言的正规表达式；(2)构造识别该语言的确定有限自...