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

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

DFA 的状态图：

0 b 1 a 2 b 3 b b b 5 b a a 4 盛威网（www.snwei.com）专业的计算机学习网站

7

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

已知 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。

答案：

先构造其矩阵 x y z 用子集法将 NFA 确定化： x z xz y xy xyz 将 x、z、xz、y、xy、xyz 重新命名，分别用 A、B、C、D、E、F 表示。因为 B、C、F

中含有 z，所以它为终态。 A B C D E F 0 B C C E F F 1 A D E A E 0 z xz xz xy xyz xyz 1 x y xy x xy 0 z x,y x,z 1 x y

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

8

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

DFA 的状态图： 1 1 0 1 D A B 0 0 E 1 C 0 0 0 F 1 第 3 题

将下图确定化：

答案：

用子集法将 NFA 确定化：

. S VQ QU VZ V QUZ Z 0 VQ VZ V Z Z VZ Z

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

. 0 1 9

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

《编译原理》课后习题答案第四章 S A B C D E F DFA 的状态图： A C D F F C F B B E F . E F

第 4 题

将下图的（a）和（b）分别确定化和最小化：

答案：

初始分划得

Π0：终态组{0}，非终态组{1,2,3,4,5} 对非终态组进行审查： {1,2,3,4,5}a {1,2,3,4,5}

{0,1,3,5} 而{0,1,3,5}既不属于{0}，也不属于

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

10

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

∵{4} a {0}，所以得到新分划

Π1：{0}，{4}，{1,2,3,5} 对{1,2,3,5}进行审查： ∵{1,5} b {2,3} b 5}，{2,3} {1, 5} a {2,3} a

{4}

{1,2,3,5}，故得到新分划 Π2：{0}，{4}，{1, {1, 5}

{1,3}，故状态 2 和状态 3 不等价，得到新分划

Π3：{0}，{2}，{3}，{4}，{1, 5} 这是最后分划了 最小 DFA：

第 5 题

构造一个 DFA，它接收Σ={0,1}上所有满足如下条件的字符串：每个 1 都有 0 直接跟在右边。并给出该语言的正规式。 答案：

按题意相应的正规表达式是(0*10)*0*，或 0*(0 | 10)*0* 构造相应的 DFA，首先构造 NFA 为

用子集法确定化：

I {X,0,1,3,Y} {0,1,3,Y} {2} {1,3,Y} 重新命名状态集：

S 0 1 11

I0 {0,1,3,Y} {0,1,3,Y} {1,3,Y} {1,3,Y} I1 {2} {2} {2}

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