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的状态图：

第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：

用子集法将NFA确定化： · 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 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

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

1 6 6 2 5

DFA的状态图： 令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。 最小化为： 0 a a 5 2 b 3 a a b 4 1 6 b a a b b b a b