编译 第二章习题课

1、1 1 ji a* i a/b j i ab j j b i a k j i a b a jik a 2 2 ij i jkl i mk lnj bb aa a|b a|b 3 3 s 31 6 5 24z a b a b a b a b 图 2.1 4 4 表表2.1 由子集法构造由子集法构造dfa 5 5 表2.2 6 6 0 a 1 2 35 46 a b ab b a b a b b a b a 图2.2 正规式 7 7 8 8 0 1 2 a 3 a,b a a b b b 图2.3正规式 9 9 解答： （1）构造转换系统如图2.4所示。 a 1 3 2 5 z b b 图2.4

2、(a*|b*)b(ba)*的转换系统 4 5 5 ba 1010 表2.3 nfa确定化为dfa的过程(并换名) i ia ib a1,2,3,4 b2,4 c3,4,5,6,z) b2,4 b2,4 d5,6,z c3,4,5,6,z e3,4,5,6,7,z d5,6,z f7 e3,4,5,6,7,z g6,z e3,4,5,6,7,z) f7 g6,z g6,z f7 1111 a c b f d e g a b b a b a b b b a 图2.5 (a*|b*)b(ba)*的dfa 1212 1313 c b a f d e a b a a a b b b b 图2.6 最小化

3、dfa 1414 6 1 2 45 3 a b a a a b b b 图 2.7 1515 i ia ib a1 b2 c4 b2 d3,6,4 e6,4 c4 - f5,4 d3,6,4 d3,6,4 g3,4,5,6 e6,4 d3,6,4 f5,4 f5,4 f5,4 h4,5,6 g3,4,5,6 g3,4,5,6 g3,4,5,6 h4,5,6 g3,4,5,6 h4,5,6 1616 a,b a h b c f e g d a b a a a a bb b b b b 图2.8 nfa的dfa 确定的dfa相应的状态图如图2.8所示。 1717 1818 e a b c d f

4、a a a a a,b b b b b b 图2.9 nfa的最小化dfa 1919 3 5 1 42 start a,b a,b a 图2.10 m1的有穷自动机 2020 2 1 3 4 5 6 7 start a a a a a aa b b b b b b b 图2.11 m2的有穷自动机 2121 i ia ib 2222 1 3 2 a,b a bb a 图2.12 m1的dfa 2323 12 a,b a b 图2.13 m1的最小化dfa 2424 12 a,b a b 图2.14 m2的最小化dfa 结论： m1、m2的最小化的最小化dfa相同，所以二者等价相同，所以二者等价

5、 2525 2626 4x6 5 01 a 23 b 输入串：ababbab 状态转换序列：x4015，4235，4015，4235， 4235，4015，4035 2727 输入串：ababbab 状态转换序列：x0,0000000,1 x01 a b 2828 2929 1 1 1 1 a a b b b b a,b 参考答案 3030 0 1 2 0 3 0,1 0 0 1 1 1 正规式 参考答案 3131 参考答案参考答案 (1) 首先构造转换系统如图所示： czsabd gf e ba a b b a 3232 （2）又转换系统构造）又转换系统构造dfa的过程如表：的过程如表： s

6、,a,b,g,f g,f a,b,c,g,f g,f g,f a,b,g,f a,b,c,g,f d,f,g,e,z a,b,c,g,f a,b,g,f g,f a,b,c,g,f d,f,g,e,z g,f,e,z a,b,e,z,g,f g,f,e,z g,f,e,z a,b,e,z,g,f a,b,e,z,g,f g,f,e,z a,b,c,e,z,g,f a,b,c,e,z,g,f d,f,g,e,z a,b,c,e,z,g,f i ia ib 3333 dfa的状态图如图：的状态图如图： 6 1 b 2 4 3 5 7 8 a b b a a b a a b a b a b a b

7、3434 (3)dfa最小化： 首先得到两个子集 k1=1,2,3,4和k2=5，6，7，8 由于状态3输入a到达k2，而状态1，2，4输入a 到达k1,所以将k1分割成k11=1，2，4和k12=3 而状态1和状态4输入a到达状态2，输入b到达状态3， 状态2输入b到达状态4，所以k11分割成 k111=1，4和k112=2 由于状态5，6，7，8输入a都到达k2,输入b都到 达k2，所以状态5，6，7，8等价。 这样，将原状态集合分割成以下子集： 1，4， 2 ， 3 ， 5，6，7，8 所以最小化dfa的状态图为： 3535 a,b 1 1 1 1 a a b b b b a,b 3636 start abc 0,10,1 1 1 3737 i i0 i1 a a a,b a,b a a,b,c a,b,c a,c a,b,c a,c a,c a,b,c 3838 1 234 0 0 1 0 1 1 1 0