电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

编译原理-试题及参考答案魏国利VIP免费

编译原理-试题及参考答案魏国利_第1页
1/9
编译原理-试题及参考答案魏国利_第2页
2/9
编译原理-试题及参考答案魏国利_第3页
3/9
1/9试题(共10道)1.设={0,1}上的正规集S由倒数第二个字符为1的所有字符串组成,请给出该字集对应的正规式,并构造一个识别该正规集的DFA。2.已知文法G[S’]:S’→SS→rDD→D,iD→i(1)构造G[S’]的识别活前缀的有穷自动机DFA。(2)该文法是LR(0)文法吗?为什么?3.已知文法G[S’]:S’→S(1)S→AAA(2)A→1A(3)A→0(4)(1)构造G[S’]的识别活前缀的有穷自动机DFA。(2)构造相应的LR(0)分析表。4.构造一个DFA,它接受={a,b}上所有包含ab的字符串。5.构造正规式(0|1)*00相应的DFA并进行化简。6.构造以下正规式相应的NFA,再确定化10(1|0)*117.设有语言L={α|α∈{0,1}+,且α不以0开头,但以00结尾}。(1)试写出描述L的正规表达式;(2)构造识别L的DFA(要求给出详细过程,并画出构造过程中的NDFA、DFA的状态转换图,以及DFA的形式化描述)。8.已知NFA=({x,y,z},{0,1},M,{x},{z}),其中:M(x,0)={z},M(y,0)={x,y},,M(z,0)={x,z},M(x,1)={x},M(y,1)=φ,M(z,1)={y},构造相应的DFA。9.给出下述文法所对应的正规式:S→0A|1BA→1S|1B→0S|02/910.将下图的DFA最小化,并用正规式描述它所识别的语言。3/9答案1.答:构造相应的正规式:(0|1)*1(0|1)NFA:11100确定化:I0I1I{0,1,2}{1,2}{1,2,3}{1,2}{1,2}{1,2,3}{1,2,3}{1,2,4}{1,2,3,4}{1,2,4}{1,2}{1,2,3}{1,2,3,4}{1,2,4}{1,2,3,4}01010001112.答:(1)G[S’]的识别活前缀的有穷自动机为:(2)该文法不是LR(0)文法,因为I3中有移进—规约冲突。0123401234I0:S’→·SS→·rDI2:S→r·DD→·D,iD→·iI4:D→i·I1:S’→S·I3:S→rD·D→D·,iI5:D→D,·iI6:D→D,i·4/93.答:(1)G[S’]的识别活前缀的有穷自动机为:(2)LR(0)分析表为:状态ACTIONGOTO01#SA0S4S3121ACC2S4S353S4S374r4r4r45S4S366r2r2r27r3r3r34.答:构造相应的正规式:(a|b)*ab(a|b)*aaabbb确定化:I0:S’→·SS→·AAAA→·1AA→·0I2:S→A·AAA→·1AA→·0I3:A→1·AA→·1AA→·0I1:S’→S·I5:S→AA·AA→·1AA→·0I6:S→AAA·I7:A→1A·I4:A→0·01236455/9I0I1I{0,1,2}{1,2,3}{1,2}{1,2,3}{1,2,3}{1,2,4,5,6}{1,2}{1,2,3}{1,2}{1,2,4,5,6}{1,2,3,5,6}{1,2,5,6}{1,2,3,5,6}{1,2,3,5,6}{1,2,4,5,6}{1,2,5,6}{1,2,3,5,6}{1,2,5,6}bbbaaaaaabbb最小化:{0,1,2}{3,4,5}{0,2},1,{3,4,5}5.答:确定化:01{1,2,3}{2,3,4}{2,3}{2,3,4}{2,3,4,5}{2,3}{2,3}{2,3,4}{2,3}{2,3,4,5}{2,3,4,5}{2,3}012345baa01b3ba1001523406/9最小化:{1,2,3}{4}{1,2,3}0={2,4}{1,3}{2}{4}6.答:01T0:{X}{A}:T1T1:{A}{B}:T2T2:{B}{B}:T2{B,C}:T3T3:{B,C}{B},T2{B,C,D}:T4T4:{B,C,D}{B}:T2{B,C,D}:T401012340011101012301101011010T0T1T2T3T410101xABC1D7/97.答:(1)正规表达式:1(0|1)*00(2)第一步:将正规表达式转换为NDFA第二步:将NDFA确定化为DFA:造表法确定化,确定化后DFAM的状态转换表状态输入I0I1t01[S]—[A,D,B]q0—q1[A,D,B][D,B,C][D,B]重新命名q1q2q3[D,B,C][D,B,C,Z][D,B]q2q4q3[D,B][D,B,C][D,B]q3q2q3[D,B,C,Z][D,B,C,Z][D,B]q4q4q3DFA的状态转换图第三步:给出DFA的形式化描述DFAM=({q0,q1,q2,q3,q4},{0,1},t,q0,{q4})t的定义见M的状态转换表。8/98.答:先构造其矩阵:用子集法将NFA确定化:将x、z、xz、y、xy、xyz重新命名,分别用A、B、C、D、E、F表示。因为B、C、F中含有z,所以它为终态。DFA的状态图:9/99.答:解方程组S的解:S=0A|1BA=1S|1B=0S|0将A、B产生式的右部代入S中S=01S|01|10S|10=(01|10)S|(01|10)所以:S=(01|10)*(01|10)10.答:

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

编译原理-试题及参考答案魏国利

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部