《编译原理-试题及答案(魏国利)》由会员分享，可在线阅读，更多相关《编译原理-试题及答案(魏国利)（9页珍藏版）》请在金锄头文库上搜索。
1、试题（共 10 道）1.设 =0，1上的正规集 S 由倒数第二个字符为 1 的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的 DFA。2.已知文法 GS :S S SrDDD,iDi(1)构造 GS的识别活前缀的有穷自动机 DFA。(2)该文法是 LR(0)文法吗？为什么？3.已知文法 GS :S S (1) SAAA (2)A1A (3)A0 (4)(1)构造 GS的识别活前缀的有穷自动机 DFA。(2)构造相应的 LR(0)分析表。4.构造一个 DFA，它接受=a，b 上所有包含 ab 的字符串。5. 构造正规式 (0|1)*00 相应的 DFA 并进行化简。6. 构造
2、以下正规式相应的 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. 给出下述文法所对应的正规式：S0A|1BA1S|1B0S|010. 将下图的
3、DFA 最小化，并用正规式描述它所识别的语言。答案1.答：构造相应的正规式：(0|1)*1(0|1) NFA: 1 1 1 0 0确定化：I 0I1I0,1,2 1,2 1,2,31,2 1,2 1,2,31,2,3 1,2,4 1,2,3,41,2,4 1,2 1,2,31,2,3,4 1,2,4 1,2,3,4010 1 0 00 11 12.答：(1) GS的识别活前缀的有穷自动机为：(2) 该文法不是 LR（0）文法，因为 I3 中有移进规约冲突。0 1 2 3 40 1 2 3 4I0: S SSrDI2: SrDDD,iDiI4: DiI1: S S I3: SrDDD,iI5:
4、DD, iI6: DD, i 3.答：(1) GS的识别活前缀的有穷自动机为：(2)LR(0)分析表为 :ACTION GOTO状态0 1 # S A0 S4 S3 1 21 ACC2 S4 S3 53 S4 S3 74 r4 r4 r45 S4 S3 66 r2 r2 r27 r3 r3 r34.答：构造相应的正规式：(a|b)*ab(a|b)*a a a b b bI0: S SSAAA A1A A0I2: SAAAA1A A0I3: A1A A1A A0I1: S SI5: SAAAA1A A0I6: SAAAI7: A1AI4: A00 1 2 3 64 5确定化：I 0I1I0,1,
5、2 1,2,3 1,21,2,3 1,2,3 1,2,4,5,61,2 1,2,3 1,21,2,4,5,6 1,2,3,5,6 1,2,5,61,2,3,5,6 1,2,3,5,6 1,2,4,5,61,2,5,6 1,2,3,5,6 1,2,5,6b bb aa a a aa b bb 最小化：0，1，2 3，4，50， 2，1 ， 3，4，55.答：确定化：0 11，2，3 2，3，4 2，32，3，4 2，3，4，5 2，32，3 2，3，4 2，30 1 2 3 4 5baa0 1b3ba10 0 1 5 2 3 402，3，4，5 2，3，4，5 2，3最小化：1，2， 3 41，
6、2， 30=2，41，3 2 46.答：0 1T0: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:T401012340 0111010 1 2 301101011 0 10T0 T1 T2 T3 T410101x A、B C1D7.答：(1) 正规表达式： 1(0|1) * 00(2) 第一步：将正规表达式转换为 NDFA 第二步：将 NDFA 确定化为 DFA ： 造表法确定化,确定化后 DFA M 的状态转换表 状态 输入 I 0 I 1 t 0 1 S A,D,B q 0 q 1 A,D,
7、B D,B,C D,B 重新命名 q 1 q 2 q 3 D,B,C D,B,C,Z D,B q 2 q 4 q 3 D,B D,B,C D,B q 3 q 2 q 3 D,B,C,Z D,B,C,Z D,B q 4 q 4 q 3 DFA 的状态转换图第三步：给出 DFA 的形式化描述 DFA M = （ q 0 , q 1 , q 2 , q 3 , q 4 , 0,1, t, q 0 , q 4 ） 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.答：
