PDF《第4章 词法分析》

0 1 A B A B C D C C E D E E F A F F E DFA 的状态图: 盛威网(www.snwei.com)专业的计算机学习网站

7 A

0 1

0 F E D

0 B

1 0

1 0

1 0

1 C 《编译原理》课后习题答案

第四章 第3题将下图确定化: 答案: 用子集法将 NFA 确定化: .

0 1 S VQ QU VQ VZ QU QU V QUZ VZ Z Z V Z . QUZ VZ QUZ Z Z Z 重新命名状态子集,令VQ 为A、QU 为B、VZ 为C、V 为D、QUZ 为E、Z 为F. .

0 1 S A B A C B B D E C F F D F . E C E F F F DFA 的状态图: 盛威网(www.snwei.com)专业的计算机学习网站

8 《编译原理》课后习题答案

第四章 第4题将下图的(a)和(b)分别确定化和最小化: 答案: 初始分划得 Π0:终态组{0},非终态组{1,2,3,4,5} 对非终态组进行审查: {1,2,3,4,5}a {0,1,3,5} 而{0,1,3,5}既不属于{0},也不属于{1,2,3,4,5} {4} a ∵ {0},所以得到新分划 Π1:{0},{4},{1,2,3,5} 对{1,2,3,5}进行审查: {1,5} b ∵ {4} {2,3} b {1,2,3,5},故得到新分划 Π2:{0},{4},{1, 5},{2,3} {1, 5} a {1, 5} {2,3} a {1,3},故状态

2 和状态

3 不等价,得到新分划 Π3:{0},{2},{3},{4},{1, 5} 这是最后分划了 盛威网(www.snwei.com)专业的计算机学习网站

9 《编译原理》课后习题答案

第四章 最小 DFA: 第5题构造一个 DFA,它接收 Σ={0,1}上所有满足如下条件的字符串:每个

1 都有

0 直接跟在 右边.并给出该语言的正规式. 答案: 按题意相应的正规表达式是(0*10)*0*, 或0*(0 | 10)*0* 构造相应的 DFA, 首先构造 NFA 为 用子集法确定化: I I0 I1 {X,0,1,3,Y} {0,1,3,Y} {2} {1,3,Y} {0,1,3,Y} {0,1,3,Y} {1,3,Y} {1,3,Y} {2} {2} {2} 重新命名状态集: S

0 1

1 2

3 4

2 2

4 4

3 3

3 DFA 的状态图: 盛威网(www.snwei.com)专业的计算机学习网站

10 《编译原理》课后习题答案

第四章 可将该 DFA 最小化: 终态组为{1,2,4},非终态组为{3},{1,2,4}0 {1,2,4},{1,2,4}1 {3},所以 1,2,4 为等价状 态,可合并. 第6题 设无符号数的正规式为θ: θ=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: X d B . d F G d H

10 d A ε C

10 d D s ε E d Y d s ε d 用子集法将 NFA 确定化: 盛威网(www.snwei.com)专业的计算机学习网站

11 《编译原理》课后习题答案

第四章 ε ・ s

10 d X XA T0=XA B F A B B F FG A A T1=B C C C T2=FG G H G G H H T3=A B F A T4=C D C D DE T5=G H T6=H H T7=DE E Y E E Y Y T8=E Y T9=Y 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. ・ s

10 d

0 1

2 3

1 4

2 5

6 3

1 2

3 4

7 4

5 6

6 6

7 8

9 8

9 9

9 DFA 的状态图: 盛威网(www.snwei.com)专业的计算机学习网站

12 《编译原理》课后习题答案

第四章 ・ d

6 5

2 d

3 d d

4 7

8 9

0 1

10 d s ・

10 10 d d s 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: S a A a Z Q b B D a E b F b b a b a a b b b b a b 用子集法将 NFA 确定化: 盛威网(www.snwei.com)专业的计算机学习网站

13 《编译原理》课后习题答案

第四章 a b S A Q A A BZ Q Q DZ BZ Q D DZ A B D A B B Q D 将S、A、Q、BZ、DZ、D、B 重新命名,分别用

0、

1、

2、

3、

4、

5、6 表示.因为

3、

4 中含有 z,所以它们为终态. a b