编译原理课后习题答案+清华大学出版社第二版

《编译原理》课后习题答案第四章 1 2 3 4 DFA 的状态图： 2 2 4 4 3 3 3

可将该 DFA 最小化：

终态组为{1,2,4}，非终态组为{3}，{1,2,4}0 {1,2,4}，{1,2,4}1 {3}，所以 1,2,4 为等价状态，可合并。

第６题

设无符号数的正规式为θ：

θ=dd*|dd*.dd*|.dd*|dd*10(s|ε)dd* |10(s|ε)dd*|.dd*10(s|ε)dd*

|dd*.dd*10(s|ε)dd*

化简θ，画出θ的DFA，其中d={0,1,2,…,9}，s={＋，－}

答案：

先构造 NFA： d . X

用子集法将 NFA 确定化： d A ε 1 0 F B d d s C G 10 D E d d Y ε s ε d H d

盛威网（www.snwei.com）专业的计算机学习网站

12

《编译原理》课后习题答案第四章 X T0=XA B F A T1=B C T2=FG G H T3=A T4=C D T5=G T6=H T7=DE E Y T8=E T9=Y 将 XA、B、FG、A、C、G、H、DE、E、Y 重新命名，分别用 0、1、2、3、4、5、6、

7、8、9 表示。终态有 0、3、4、6、9。 0 1 2 3 4 · 1 1 s 5 10 2 2 7 d 3 4 6 3 4 13

ε XA B FG A C G H DE E Y · B B s G E 10 F F D d A C H A C H H Y Y Y

盛威网（www.snwei.com）专业的计算机学习网站

《编译原理》课后习题答案第四章 5 6 6 6 7 8 9 8 9 9 9 DFA 的状态图：

d · d 4 1 0 · 1 7 s 0 1 0 s 2 5 8 d 1 0 d d d d 3 6 9 d d d 第 7 题

给文法 G[S]： S→aA|bQ

A→aA|bB|b B→bD|aQ Q→aQ|bD|b D→bB|aA E→aB|bF

F→bD|aE|b 构造相应的最小的 DFA。 答案：

先构造其 NFA：

盛威网（www.snwei.com）专业的计算机学习网站

14

《编译原理》课后习题答案第四章

S A Q BZ DZ D B 0 1 2 3 4 5 6

a b S b a Q a b D b a A a b B a b E b a F Z b b b 用子集法将 NFA 确定化： a A A Q Q A A Q b Q BZ DZ D B B D 将 S、A、Q、BZ、DZ、D、B 重新命名，分别用 0、1、2、3、4、5、6 表示。因为

3、

4 中含有 z，所以它们为终态。 a 1 1 2 2 1 1 2 DFA 的状态图：

b 2 3 4 5 6 6 5

盛威网（www.snwei.com）专业的计算机学习网站

15

《编译原理》课后习题答案第四章

a a 0 1 a a b b 5 b 4 2 b b

a 3 a a b 6 b

令P0＝（｛0,1,2,5,6｝,｛3,4｝）用b进行分割： P1＝（｛0,5, 6｝,｛1,2｝,｛3,4｝）再用b进行分割：

P2＝（｛0｝,｛5, 6｝,｛1,2｝,｛3,4｝）再用a、b 进行分割，仍不变。再令｛０｝为 A，｛1，2｝为 B，｛3，4｝为 C，｛5，6｝为 D。

最小化为：

a a , b A B a b a b D b C 第８题 给出下述文法所对应的正规式：

S→0A|1B A→1S|1 B→0S|0 答案：

盛威网（www.snwei.com）专业的计算机学习网站

16