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

试题（共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 1 2 3

0 0 肯定化： I I0 I1 {0,1,2} {1,2} {1,2,3} {1,2,4} {1,2,3,4} {1,2} {1,2} {1,2,4} {1,2} {1,2,4} {1,2,3} {1,2,3} {1,2,3,4} {1,2,3} {1,2,3,4} 4

0

1 0 1 0 0 0 1 2 3 4

0 1 1 1

2.答：

(1) G[S’]的识别活前缀的有穷自动机为： I3: S→rD· I5: D→D, ·i I1: S’ →S· D→D·,i I0: S’ →·S I2: S→r·D I4: D→i· S→·rD D→·D,i D→·i (2) 该文法不是LR（0）文法，因为I3中有移进—规约冲突。

I6: D→D, i·