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

试题（共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，再确定化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 最小化，并用正规式描述它所识别的语言。答案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的识别活前缀的有穷自动机为：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,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:T2T2: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,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.答