编译 第二章习题课.ppt

《编译 第二章习题课.ppt》由会员分享，可在线阅读，更多相关《编译 第二章习题课.ppt（42页珍藏版）》请在三一办公上搜索。

1、第二章习题课,例一：现有正规式(a|b)*(aa|bb)(a|b)*，请为其构造最小化的DFA。解答：由正规式得到NFA的转换系统如图2.1所示。由子集法构造DFA如表2.1所式。,j,k,表2.1 由子集法构造DFA,由转换系统构造DFA：（i）=a,b（ii）S=-CLOSURE（S,3,1）=S,3,1,记作组合状态S，3，1（iii）确定S,F,f:为简化起见，将各组合状态换名，则表2.1变为表2.2。,表2.2,观察表2.2有 S=0,1,2,3,4,5,6 F=3,4,5,6 f的映像见表2.2（iv）所构造的DFA相应的状态图如图2.2所示。,（v）对DFA进行最小化，过程如下：

2、已知S=0,1,2,3,4,5,6，首先将S分为两个子集：S1=0，1，2（非终态集）S2=3,4,5,6（终态集）在S1=0，1，2中，因为 0，2a=1包含于S1 1a=3包含于S2 所以将S1再分为S11=0,2,S12=3 在S11=0,2中，因为有 0b=2包含于S11 2b=4包含于S2 所以将S11分为0和2两个集合，即S1分为三个不相交的子集0、1、2。,在S2=3，4，5，6中，因为有：S2a=3，6包含于S2 S2b=4，5包含于S2 所以3，4，5，6均等价，即S2不能再分，用3代替，原来出入于S2的箭弧全部引向3状态，集合内部的转换成为自循环，改造以后的DFA如图2.3

3、。,例二、请构造与正规式R=(a*|b*)b(ba)*等价的状态最少的DFA（确定的有穷自动机）,解答：（1）构造转换系统如图2.4所示。,a,(2)NFA确定化为DFA的过程如表2.3所示。,相应的状态转化图如图2.5所示。,(3)DFA最小化 首先得到两个子集：Sl=A,B,F和S2=C,D,E,G 由于状态A和状态B有b输入，状态F无b输入，所 以将K1分割成 S11=A，B)，S12=F)由于状态C、D、G无a输入，而状态E有a输入，所以S2分割成 S21=(C，D，G和S22=E 又由于状态C输入b到达E，状态D、G输入b到达F，所以将K21分割成 S211=C和S212=D，G 由

4、于状态A输入b到达C，状态B输入b到达D，所以将S11分割成:S11=A和S112=B),S11=A和S112=B)所以，原DFA的状态集合被划分为 A、B、F、E、C和D，G最小化DFA的状态图如图2.6所示。,例三、将图2.7所示的非确定有穷自动机（NFA）变换成等价的有穷自动机（DFA）。其中1为初态，6为终态。,解答：用子集法将NFA确定化为DFA的过程如表2.4所示。,确定的DFA相应的状态图如图2.8所示。,DFA最小化：首先得到两个子集 S1=A,B,C,F和S2=(D,E,G,H)由于状态A，B，F有输入a，而状态C无输入a，所以将S1分割成 S11=A,B,F 和S12=C又

5、由于状态A输入a到达B S11，状态B输入a到达D S2，状态F输入a到达F S11，所以状态A和状态F与状态B不等价。又状态A输入b到达C，状态F输入b到达H，所以状态A和状态H不等价。所以将S11分割成 S111=A S112=B S113=F 由于状态D，G，H输入a都到达S2，输入b都到达S2，而状态E输入b却到达F Sll3，所以，D，G，H等价，但它们与E是可分的，将K2分割成 S21=D，G，H S22=E,这样，将原状态集合分割成以下子集：A B C E F D,G,H最小化DFA的状态图如图2.9所示。,例四、图所示的两个有穷自动机M1和M2是否等价？,解答：如果难以直接从图

6、中判断，也可求出最小化DFA进行判断。对于M1，用子集法将求DFA的过程如表2.5所示。,相应的状态图如图2.12所示。,对DFA最小化：首先得到两个子集 S1=1,3和S2=2由于状态1和状态3输入a都到达状态2，输入b都到达状态3，所以状态1和状态3等价。这样，将原状态集合分割成以下子集：1，3、2),所以，最小化DFA的状态图如图2.13所示。,对于M2，因为M2已是DFA，所以对其进行最小化：首先得到两个子集 S1=1,3和S2=2,4,5,6,7 由于状态2、4、5、6、7输入a都到达S2，输入b都到达S2，所以状态2、4、5、6、7等价。又状态1和状态3输入a都到达S2，输入b都到

7、达S1，所以状态1和状态3等价。,这样，将原状态集合分割成私下子集：1，3，2，4，5，6，7)所以，最小化DFA的状态图如图2.14所示(已换名).,结论：M1、M2的最小化DFA相同，所以二者等价,习题提示,2.4（a）以0开头，0结尾的所有由0和1组成的数字串。（b）长度可以为0的所有0和1 组成的数字串（c）长度大于等于3，且倒数第三位为0的所有数字串（d）至少包括3个1的所有由0和1组成的数字串（e）0和1的个数都是偶数的所有的0和1 组成的数字串2.5（a）设 字母表1=ab,2=a,e,I,o,u,=1-2,digit1正规定义为上的任意一个元素，则本题的正规式为：digit1*

8、(a?)digit1*(e?)digit1*(i?)digit1*(o?)digit1*(u?)digit1*,2.8(1)(a|b)*,输入串：ababbab状态转换序列：X4015，4235，4015，4235，4235，4015，4035,输入串：ababbab状态转换序列：X0,0000000,1,课堂练习,1、请构造与正规式R=(a*b)*ba(a|b)*等价的状态最少的DFA.2、有穷状态自动机M接受字母表=0，1上所有满足条件的串，串中至少要包含两个连续的0或两个连续的1。（1）请给出与等价的正规式（2）将最小化,参考答案,0,0,1,0,0,1,1,1,正规式(0|1)*(00

9、|11)(0|1)*的最小化DFA,参考答案,参考答案,(1)首先构造转换系统如图所示：,(a*b)*ba(a|b)*的转换系统,（2）又转换系统构造DFA的过程如表：,S,A,B,G,F G,F A,B,C,G,FG,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,

10、Z,G,F,I Ia Ib,DFA的状态图如图：,(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的状态图为：,a,b,例五、已知有限自动机如图所示。（1）状态转换图表示

11、的语言有什么特点？（2）写出表示该语言的正规式。（3）构造识别该语言的有限状态自动机DFA。,解答:,表示所有的至少包括两个连续的1的由0和1组成的字符串.正规式:(0|1)*11(0|1)*构造有限自动机:前图NFA到DFA的确定化过程如表:,相应DFA的状态图如图:,DFA最小化:首先得到两个子集:K1=1,2 K2=3,4 由于状态1输入1到达K1,而状态2输入1到达K2,所以将K1分为 K11=1 和 K12=2 由于状态3,4输入0到达K2,输入1也到达K2,所以状态3和4等价.这样,将原状态集合分割成:1,2,3,4所以最小状态集合如图:,课堂练习,1、设字母表为a,b,给出正规式:b*abb*(abb*)*(1)构造该正规式所对应的NFA(画出转换图)(2)将所求得的NFA确定化(画出DFA的转换图)(3)将所求得的DFA最小化(画出极小化的转换图)(4)该正规式所表示的正规式是什么?试用自然语言描述之.2、试求与如图相类似的DFA。,0,1,0,1,0,1,0,0,1,1,1,0,参考答案,1、b*abb*(abb*)*,2、参考答案,