编译原理-试题及答案(魏国利)

试题（共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|010.将下图的DFA最小化，并用正规式描述它所识别的语言。答案1.答：构造相应的正规式：(0|1)*1(0|1)NFA:11100确定化：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·3.答：(1)G[S’]的识别活前缀的有穷自动机为：(2)LR(0)分析表为:状态ACTIONGOTO01#SA0S4S3121ACC2S4S353S4S374r4r4r45S4S366r2r2r27r3r3r34.答：构造相应的正规式：(a|b)*ab(a|b)*aaabbb确定化：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·0123645I0I1I{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}012345baa01b3ba100152340最小化：{1，2，3}{4}{1，2，3}0={2，4}{1，3}{2}{4}6.答：01T0:{X}{A}:T1T1:{A}{B}:T2T2:{B}{B}:T2{B,C}:T3T3:{B,C}{B},T2{B,C,D}:T4T4:{B,C,D}{B}:T2{B,C,D}:T401012340011101012301101011010T0T1T2T3T410101xA、BC1D7.答：(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.答：先构造其矩阵:用子集法将NFA确定化：将x、z、xz、y、xy、xyz重新命名，分别用A、B、C、D、E、F表示。因为B、C、F中含有z，所以它为终态。DFA的状态图：9.答：解方程组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.答：