《编译原理-试题及答案(魏国利).doc》由会员分享,可在线阅读,更多相关《编译原理-试题及答案(魏国利).doc(9页珍藏版)》请在金锄头文库上搜索。
1、试题(共10道)1.设S=0,1上的正规集S由倒数第二个字符为1的所有字符串组成,请给出该字集对应的正规式,并构造一个识别该正规集的DFA。2.已知文法GS :S S SrD DD,i Di(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,它接受S=a,b上所有包含ab的字符串。5. 构造正规式 (0|1)*00 相应的DFA并进行化简。6. 构造以下正规式相应的NFA,再确定化
2、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. 将下图的 DFA 最小化,并用正规式描述它所识别的语
3、言。答案1.答:构造相应的正规式:(0|1)*1(0|1) NFA: 1 110432 e e e e 1 0 0确定化:I0,1,21,21,2,31,21,21,2,31,2,31,2,41,2,3,41,2,41,21,2,31,2,3,41,2,41,2,3,4 0 143210 0 1 0 0 0 1 1 12.答: (1) GS的识别活前缀的有穷自动机为:I6: DD, iI5: DD, iI3: SrD DD,iI1: S SI0: S S SrDI4: DiI2: SrD DD,i Di(2) 该文法不是LR(0)文法,因为I3中有移进规约冲突。 3.答: (1) GS的识别活
4、前缀的有穷自动机为:I5: SAAA A1A A0I6: SAAAI1: S SI0: S S SAAA A1A A0I2: SAAA A1A A0I4: A0I7: A1AI3: A1A A1A A0(2) LR(0)分析表为:状态ACTIONGOTO01#SA0S4S3121ACC2S4S353S4S374r4r4r45S4S366r2r2r27r3r3r34.答:构造相应的正规式:(a|b)*ab(a|b)*0123645 a a e e a b e e b b确定化:I0,1,21,2,31,21,2,31,2,31,2,4,5,61,21,2,31,21,2,4,5,61,2,3,5
5、,61,2,5,61,2,3,5,61,2,3,5,61,2,4,5,61,2,5,61,2,3,5,61,2,5,6 b b b a543210 a a a a a b b b 最小化:0,1,2 3,4,50, 2,1, 3,4,5baa01b3ba5.答:10e0e 1 5 2 3 40确定化:011,2,32,3,42,32,3,42,3,4,52,32,32,3,42,32,3,4,52,3,4,52,3010 1 2 3 400111最小化:1,2,3 41,2,30=2,41,3 2 4010 1 2 30116.答:10101xA、BC1D01T0:XA :T1T1:AB:T2
6、T2:BB:T2B,C:T3T3:B,CB,T2B,C,D:T4T4:B,C,DB:T2B,C,D:T41011010T0T1T2T3T407.答:(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,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
7、,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.答: