编译原理第3章文法和语言 下载本文

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进行分割,仍不变。 再令{0}为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