清华大学第二版编译原理答案
b a b
第２题
已知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。 答案：
先构造其矩阵 0 1 x z x y x,y z x,z y
用子集法将NFA 确定化： 0 1 x z x z xz y xz xz xy y xy xy xyz x xyz xyz xy
将x、z、xz、y、xy、xyz 重新命名，分别用A、B、C、D、E、F 表示。因为B、C、F 中含有z，所以它为终态。 0 1 A B A B C D C C E D E E F A F F E
DFA 的状态图： 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 的状态图： 第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} 这是最后分划了 最小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 的状态图：
可将该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： X d
清华大学第二版编译原理答案
. B d F G d H 10 d A ε C 10 d D s
ε E d Y d s ε d
用子集法将NFA 确定化： ε ? 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 的状态图： ? d 6 2 5 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