编译 第二章习题课.ppt

1 第二章习题课第二章习题课 例一：现有正规式例一：现有正规式( (a|b)*(aa|bb)(a|b)*a|b)*(aa|bb)(a|b)*，请为其请为其 构造最小化的构造最小化的dfadfa。 解答：由正规式得到解答：由正规式得到nfanfa的转换系统如图的转换系统如图2.12.1所示。所示。 由子集法构造由子集法构造dfadfa如表如表2.12.1所式。所式。 ji a* i a/b j i ab j j b i a k j i a b a ji k a 2 i ( (a|b)*(aa|bb)(a|b)*a|b)*(aa|bb)(a|b)* j i ( (a|b)*a|b)* ( (a|b)*a|b)* jk aa|bbaa|bb l i mk lnj bb aa a|b a|b 3 s 31 6 5 24z a b a b a b a b 图 2.1 4 i i i i a a i i b b s s ,3,1,3,13,5,13,5,13,6,13,6,1 3,5,13,5,13,5,2,1,4,3,5,2,1,4,z z 3,6,13,6,1 3,6,13,6,13,5,13,5,13,6,2,1,4,3,6,2,1,4,z z 3,5,2,1,4,3,5,2,1,4,z z 3,5,2,1,4,3,5,2,1,4,z z 3,6,1,4,3,6,1,4,z z 3,6,2,1,4,3,6,2,1,4,z z 3,5,1,4,3,5,1,4,z z 3,5,2,1,4,3,5,2,1,4,z z 3,6,1,4,3,6,1,4,z z 3,5,1,4,3,5,1,4,z z 3,6,2,1,4,3,6,2,1,4,z z 3,5,1,4,3,5,1,4,z z 3,5,2,1,4,3,5,2,1,4,z z 3,6,1,4,3,6,1,4,z z 表2.1 由子集法构造dfa 5 由转换系统构造由转换系统构造dfadfa： （i i）=a,ba,b （ii ii）s=-closures=-closure（ s s ,3,1,3,1）= = s s ,3,1,3,1,记作组记作组 合状态合状态 s s ，3 3，11 （iii iii）确定确定s,f,f: s,f,f: 为简化起见，将各组合状态换名，为简化起见，将各组合状态换名， 则表则表2.12.1变为表变为表2.22.2。 i i iaiaibib 0 0 1 1 2 2 1 1 3 3 2 2 2 2 1 1 4 4 3 3 3 3 5 5 4 4 6 6 4 4 5 5 6 6 4 4 6 6 3 3 5 5 表2.2 6 观察表观察表2.22.2有有 s=0,1,2,3,4,5,6s=0,1,2,3,4,5,6 f=3,4,5,6 f=3,4,5,6 f f的映像见表的映像见表2.22.2 （iv iv）所构造的所构造的dfadfa相应的状态图如图相应的状态图如图2.22.2所示。所示。 0 a 1 2 35 46 a b ab b a b a b b a b a 图2.2 正规式( (a|b)*(aa|bb)(a|b)*a|b)*(aa|bb)(a|b)*的的dfadfa 7 （v v）对对dfadfa进行最小化，过程如下：进行最小化，过程如下： 已知已知s=0,1,2,3,4,5,6s=0,1,2,3,4,5,6，首先将首先将s s分为两个子集分为两个子集 ： s s 1 1 =0=0，1 1，2 2 （非终态集）非终态集） s s 2 2 =3,4,5,6 =3,4,5,6 （终态集）终态集） 在在s1=0s1=0，1 1，22中，因为中，因为 0 0，22 a a =1=1包含于包含于s s 1 1 1 1 a a =3=3包含于包含于s s 2 2 所以将所以将s s 1 1 再分为再分为s s1111=0,2, s=0,2, s1212=3=3 在在s s1111=0,2=0,2中，因为有中，因为有 0 0 b b =2=2包含于包含于s s1111 2 2 b b =4=4包含于包含于s s 2 2 所以将所以将s s1111分为分为00和和22两个集合，即两个集合，即s s 1 1 分为三分为三 个不相交的子集个不相交的子集00、11、22。 8 在在s s 2 2 =3=3，4 4，5 5，66中，因为有：中，因为有： s s2a2a=3=3，66包含于包含于s s 2 2 s s2b2b=4=4，55包含于包含于s s 2 2 所以所以3 3，4 4，5 5，6 6均等价，即均等价，即s s 2 2 不能再分，用不能再分，用3 3代代 替，原来出入于替，原来出入于s s 2 2 的箭弧全部引向的箭弧全部引向3 3状态，集合内状态，集合内 部的转换成为自循环，改造以后的部的转换成为自循环，改造以后的dfadfa如图如图2.32.3。 0 1 2 a 3 a,b a a b b b 图2.3正规式( (a|b)*(aa|bb)(a|b)*a|b)*(aa|bb)(a|b)*的最小化的最小化dfadfa 9 例二、请构造与正规式例二、请构造与正规式r=(a*|b*)b(ba)*r=(a*|b*)b(ba)*等价的等价的 状态最少的状态最少的dfadfa（确定的有穷自动机）确定的有穷自动机） 解答： （1）构造转换系统如图2.4所示。 a 1 3 2 5 z b b 图2.4 (a*|b*)b(ba)*的转换系统 4 5 5 b a 10 (2)(2)nfanfa确定化为确定化为dfadfa的过程如表的过程如表2.32.3所示。所示。 表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 11 相应的状态转化图如图相应的状态转化图如图2.52.5所示。所示。 a c b f d e g a b b a b a b b b a 图2.5 (a*|b*)b(ba)*的dfa 12 (3)(3)dfadfa最小化最小化 首先得到两个子集：首先得到两个子集： s s l l =a,b,f=a,b,f和和s s 2 2 =c,d,e,g=c,d,e,g 由于状态由于状态a a和状态和状态b b有有b b输入，状态输入，状态f f无无b b输入，所输入，所 以将以将k1k1分割成分割成 s s1111=a=a，b)b)， s s1212=f)=f) 由于状态由于状态c c、d d、g g无无a a输入，而状态输入，而状态e e有有a a输入，所输入，所 以以s s 2 2 分割成分割成 s s2121=(c=(c，d d，gg和和s s2222=e=e 又由于状态又由于状态c c输入输入b b到达到达e e，状态状态d d、g g输入输入b b到达到达f f ，所以将所以将k21k21分割成分割成 s s211211=c=c和和s s212212=d=d，gg 由于状态由于状态a a输入输入b b到达到达c c，状态状态b b输入输入b b到达到达d d，所以所以 将将s s1111分割成分割成: : s s1111 =a =a和和s s112112= = b)b) 13 s s 1111 =a =a和和s s112112= = b)b) 所以，原所以，原dfadfa的状态集合被划分为的状态集合被划分为 aa、bb、ff、ee、cc和和 d d，gg 最小化最小化dfadfa的状态图如图的状态图如图2.62.6所示。所示。 c b a f d e a b a a a b b b b 图2.6 最小化dfa 14 n n 例三、将图例三、将图2.72.7所示的非确定有穷自动机（所示的非确定有穷自动机（nfanfa） 变换成等价的有穷自动机（变换成等价的有穷自动机（dfadfa）。）。其中其中1 1为初态为初态 ，6 6为终态。为终态。 6 1 2 45 3 a b a a a b b b 图 2.7非确定有穷自动机（非确定有穷自动机（nfanfa） 15 解答：用子集法将解答：用子集法将nfanfa确定化为确定化为dfadfa的过程如表的过程如表2.42.4 所示。所示。 表表2.4 2.4 nfanfa确定化为确定化为dfadfa的过程的过程 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 16 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所示。 17 dfadfa最小化：最小化： 首先得到两个子集首先得到两个子集 s1=a,b,c,fs1=a,b,c,f和和s2=(d,e,g,h)s2=(d,e,g,h) 由于状态由于状态a a，b b，f f有输入有输入a a，而状态而状态c c无输入无输入a a，所以所以 将将s1s1分割成分割成 s11=a,b,f s11=a,b,f 和和s12=cs12=c 又由于状态又由于状态a a输入输入a a到达到达b b s11 s11，状态状态b b输入输入a a到达到达d d s2 s2 ，状态状态f f输入输入a a到达到达f f s11 s11 ，所以状态所以状态a a和状态和状态f f 与状态与状态b b不等价。又状态不等价。又状态a a输入输入b b到达到达c c，状态状态f f输入输入 b b到达到达h h，所以状态所以状态a a和状态和状态h h不等价。所以将不等价。所以将s11s11分分 割成割成 s111=a s112=b s113=fs111=a s112=b s113=f 由于状态由于状态d d，g g，h h输入输入a a都到达都到达s2s2，输入输入b b都到达都到达 s2s2，而状态而状态e e输入输入b b却到达却到达f f sll3 sll3，所以，所以，d d，g g， h h等价，但它们与等价，但它们与e e是可分的，将是可分的，将k2k2分割成分割成 s21=ds21=d，g g，hh s22=e s22=e 18 这样，将原状态集合分割成以下子集：这样，将原状态集合分割成以下子集： a b c e f d,g,ha b c e f d,g,h 最小化最小化dfadfa的状态图如图的状态图如图2.92.9所示。所示。 e a b c d f a a a a a,b b b b b b 图2.9 nfa的最小化dfa 19 n n 例四、图所示的两个有穷自动机例四、图所示的两个有穷自动机m1m1和和m2m2 是否等价？是否等价？ 3 5 1 42 start a,b a,b a 图2.10 m1的有穷自动机 20 2 1 3 4 5 6 7 start a a a a a aa b b b b b b b 图2.11 m2的有穷自动机 21 解答：如果难以直接从图中判断，也可求出最小化解答：如果难以直接从图中判断，也可求出最小化 dfadfa进行判断。进行判断。 对于对于m1m1，用子集法将求用子集法将求dfadfa的过程如表的过程如表2.52.5所示。所示。 表表2.5 2.5 nvanva确定化为确定化为dfadfa的过程的过程( (并换名并换名) ) i ia ib a1,2,4 b2,3,4,5 c2,4a1,2,4 b2,3,4,5 c2,4 b2,3,4,5 b2,3,4,5 b2,3,4,5b2,3,4,5 b2,3,4,5 b2,3,4,5 c2,4 b2,3,4,5 c2,4 c2,4 b2,3,4,5 c2,4 相应的状态图如图相应的状态图如图2.122.12所示。所示。 22 对对dfadfa最小化：最小化： 首先得到两个子集首先得到两个子集 s1=1,3s1=1,3和和s2=2s2=2 由于状态由于状态1 1和状态和状态3 3输入输入a a都到达状态都到达状态2 2，输入，输入b b都到都到 达状态达状态3 3，所以状态，所以状态1 1和状态和状态3 3等价。这样，将原状等价。这样，将原状 态集合分割成以下子集：态集合分割成以下子集： 1 1，33、2)2) 1 3 2 a,b a bb a 图2.12 m1的dfa 23 所以，最小化所以，最小化dfadfa的状态图如图的状态图如图2.132.13所示。所示。 对于对于m2m2，因为因为m2m2已是已是dfadfa，所以对其进行最小化所以对其进行最小化 ： 首先得到两个子集首先得到两个子集 s1=1,3s1=1,3和和s2=s2=2,4,5,6,72,4,5,6,7 由于状态由于状态2 2、4 4、5 5、6 6、7 7输入输入a a都到达都到达s2s2，输入输入b b 都到达都到达s2s2，所以状态所以状态2 2、4 4、5 5、6 6、7 7等价。等价。 又状态又状态1 1和状态和状态3 3输入输入a a都到达都到达s2s2，输入输入b b都到达都到达s1s1 ，所以状态所以状态1 1和状态和状态3 3等价。等价。 12 a,b a b 图2.13 m1的最小化dfa 24 这样，将原状态集合分割成私下子集：这样，将原状态集合分割成私下子集： 1 1，33，22，4 4，5 5，6 6，7) 7) 所以，最小化所以，最小化dfadfa的状态图如图的状态图如图2.142.14所示所示( (已换名已换名) ). . 12 a,b a b 图2.14 m2的最小化dfa 结论： m1、m2的最小化dfa相同，所以二者等价 25 习题提示习题提示 2.42.4 （a a）以以0 0开头，开头，0 0结尾的所有由结尾的所有由0 0和和1 1组成的数字串。组成的数字串。 （b b）长度可以为长度可以为0 0的所有的所有0 0和和1 1 组成的数字串组成的数字串 （c c）长度大于等于长度大于等于3 3，且倒数第三位为，且倒数第三位为0 0的所有数字串的所有数字串 （d d）至少包括至少包括3 3个个1 1的所有由的所有由0 0和和1 1组成的数字串组成的数字串 （e e）0 0和和1 1的个数都是偶数的所有的的个数都是偶数的所有的0 0和和1 1 组成的数字串组成的数字串 2.52.5 （a a）设设 字母表字母表1=1=a ab b, 2=, 2=a,e,i,o,u,a,e,i,o,u, = = 1-1- 2, 2, digit1digit1正规定义为正规定义为 上的任意一个元素，则本题的正规上的任意一个元素，则本题的正规 式为：式为： digit1*(a?) digit1*(e?) digit1*(i?) digit1*(o?) digit1*(a?) digit1*(e?) digit1*(i?) digit1*(o?) digit1*(u?) digit1*digit1*(u?) digit1* 26 2.82.8 (1) (a|b)* (1) (a|b)* 4x6 5 01 a 23 b 输入串：ababbab 状态转换序列：x4015，4235，4015，4235 ，4235，4015，4035 27 输入串：ababbab 状态转换序列：x0,0000000,1 x01 a b 28 课堂练习课堂练习 1 1、请构造与正规式、请构造与正规式r=(a*b)*ba(a|b)*r=(a*b)*ba(a|b)*等价的等价的 状态最少的状态最少的dfa.dfa. 2 2、有穷状态自动机有穷状态自动机mm接受字母表接受字母表=0=0，11上上 所有满足条件的串，串中至少要包含两个所有满足条件的串，串中至少要包含两个 连续的连续的0 0或两个连续的或两个连续的1 1。 （1 1）请给出与等价的正规式）请给出与等价的正规式 （2 2）将最小化）将最小化 29 1 1 1 1 a a b b b b a,b 参考答案 30 0 1 2 0 3 0,1 0 0 1 1 1 正规式(0(0|1)*(00|11)(0|1)*|1)*(00|11)(0|1)*的最小化 的最小化dfadfa 参考答案 31 参考答案 (1) 首先构造转换系统如图所示： czsabd gf e ba a b b a (a*b)*ba(a|b)*(a*b)*ba(a|b)*的转换系统的转换系统 32 （2）又转换系统构造dfa的过程如表： s,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 33 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 34 (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的状态图为： 35 a,b 1 1 1 1 a a b b b b a,b 36 例五、已知有限自动机如图所示。例五、已知有限自动机如图所示。 （1 1）状态转换图表示的语言有什么特点？）状态转换图表示的语言有什么特点？ （2 2）写出表示该语言的正规式。）写出表示该语言的正规式。 （3 3）构造识别该语言的有限状态自动机）构造识别该语言的有限状态自动机dfadfa。 start abc 0,10,1 1 1 37 解答解答: : (1)(1)表示所有的至少包括两个连续的表示所有的至少包括两个连续的1 1的由的由0 0和和1 1 组成的字符串组成的字符串. . (2)(2)正规式正规式: (0|1)*11(0|1)*: (0|1)*11(0|1)* (3)(3)构造有限自动机构造有限自动机: : 前图前图nfanfa到到dfadfa的确定化过的确定化过 程如表程如表: : 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 38 相应相应df