DOC《第四章参考答案》

第四章参考答案 第1题: (1) 0,1

1 1

0 1 Y 确定化

0 1 X A A A AB AB AC AB AC A ABY ABY AC AB 重新命名,令AB为B、AC为C、ABY为D

0 1 X A A A B B C B C A D D C B DFA:1

0 1

1 1

0 1 D

0 0 第2题:

0 1 X A Z X Z B XZ Y XZ C XZ XY Y D XY XY E XYZ X XYZ F XYZ XY 以A、B、C、D、E、F代替X, Z, XZ, Y, XY, XYZ得DFA 其中A为初态,B,C,F为终态

0 1 A B A B C D C C E D E E F A F F E 第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题: (1) a b

0 01

1 01

01 1

1 0 以A、B、C代替

0、

01、1得DFA a b A B C B B C C A DFA图为: (2) 初始分划得 Π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题: 按题意相应的正规表达式是0*(0 | 10)*0*或0*( 100*)*0* 构造相应的DFA,首先构造NFA为000εεεεY10用子集法确定化 I I0 I1 S

0 1 {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}

1 2

3 4

2 2

4 4

3 3

3 DFA为0102110140可最小化,终态组为{1,2,4},非终态组为{3},{1,2,4}0{1,2,4},{1,2,4}1{3},所以1,2,4为等价状态,可合并.

0 1 1,2,4

0 第7题 根据文法构造NFA 确定化 a b --( a b S A Q 0初态

1 2 A A BZ

1 1

3 Q Q DZ

2 2

4 BZ Q D 3终态

2 5 DZ A B 4终态

1 6 D A B

5 1

6 B Q D

6 2

5 最小化: 将各状态划分为{0,1,2,5,6}和{3,4} 1,2经过b到达{3,4},而0,5,6经过b到达{2

5 6},所以细分为 {0

5 6}{1 2}{3 4} 0经过b到达{2},5 6经过b到达{5 6},所以细分为 {0}{5 6}{1 2}{3 4} 到此,集合不能再细分 最小化的DFA为: