编译原理-试题及答靶赂(魏国利).docVIP

试题（共10道） 1.设?={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。 2.已知文法G[S’] :S’ →S S→rD D→D,i D→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）*11 7. 设有语言 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|1B A→1S|1 B→0S|0 10. 将下图的 DFA 最小化，并用正规式描述它所识别的语言。 答案 1.答： 构造相应的正规式：(0|1)*1(0|1) NFA: 1 1 1 0 4 3 2 ? ? ? ? 1 0 0 确定化： I{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} 0 1 4 3 2 1 0 0 1 0 0 0 1 1 1 2.答： (1) G[S’]的识别活前缀的有穷自动机为： I6: D→D, i· I5: D→D, ·i I3: S→rD· D→D·,i I1: S’ →S· I0: S’ →·S S→·rD I4: D→i· I2: S→r·D D→·D,i D→·i (2) 该文法不是LR（0）文法，因为I3中有移进—规约冲突。 3.答： (1) G[S’]的识别活前缀的有穷自动机为： I5: S→AA·A A→·1A A→·0 I6: S→AAA· I1: S’ →S· I0: S’ →·S S→·AAA A→·1A A→·0 I2: S→A·AA A→·1A A→·0 I4: A→0· I7: A→1A· I3: A→1·A A→·1A A→·0 (2) LR(0)分析表为: 状态ACTIONGOTO01#SA0S4S3121ACC2S4S353S4S374r4r4r45S4S366r2r2r27r3r3r3 4.答： 构造相应的正规式：(a|b)*ab(a|b)*