编译原理第3章文法和语言(6)

4 3 5 4 2 3 5 2 3

DFA的状态图： X A b εB a

F b G b H E ε Y a ε

C D bε I b ε ε ε ε

0 b 1 b 2 a 4 5 3 b b a 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