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