第三章-词法分析作业答案

1.求正则式（a|b)(a|b|0|1)*对应的正则文法（右线性文法），画状态转换图。解:(a|b):Sa|b(a|b|0|1)*:AaA|bA|0A|1A合并:Sa|bAaA|bA|0A|1A|εSABZa,b,0,1abεε2、求正则文法G[Z]：Z0Z|1Z|0AA0BB0对应的正则式:解:(0|1)*0002.已知有限自动机如图(1)以上状态转换图表示的语言有什么特征？(2)写出其正规式与正规文法.(3)构造识别该语言的有限自动机DFA.解：（1）L={W|W{0,1},并且W至少有两个连续的1}（2）正则式为（0|1)*11(0|1)*正则文法G(Z)为：Z0Z|1Z|1AA1B|1B0B|1B|0|1（3）将图中有限自动机确定化：首先从处态A出发：II0I1(1){A}(1){A}(2){A,B}(2){A,B}(1){A}(3){A,B,C}(3){A,B,C}(4){A,C}(3){A,B,C}(4){A,C}(4){A,C}(3){A,B,C}其相应的DFA如下图：将这个DFA最小化：首先分终态和非终态两个集K1={1,2}和K2={3,4}由于状态1输入1到达状态K1集，而状态2输入1到达K2集故将k1分为K11={1},K12={2}由于状态3，和4输入1，或0都到达k2集所以状态3，4等价。则可以分割成三个子集：{1}，{2}，{3，4}所以将DFA最小化的状态图如下：3.请构造与正则式R=(a*b)*ba(a|b)*等价的状态最少的DFA（确定有限自动机）解：（1）首先构造转换系统图：（2）由系统转换图构造DFA（NFA确定化）设初态为[S,A,B,G,F]NFA确定化为DFA的过程：IIaIb(1)[S,A,B,G,F](2)[G,F](3)[A,B,C,G,F](2)[G,F](2)[G,F](4)[A,B,G,F](3)[A,B,C,G,F](5)[D,F,G,E,Z](3)[A,B,C,G,F](4)[A,B,G,F](2)[G,F](3)[A,B,C,G,F](5)[D,F,G,E,Z](6)[G,F,E,Z](7)[A,B,E,Z,G,F](6)[G,F,E,Z](6)[G,F,E,Z](7)[A,B,E,Z,G,F](7)[A,B,E,Z,G,F](6)[G,F,E,Z](8)[A,B,C,E,Z,G,F](8)[A,B,C,E,Z,G,F](5)[D,F,G,E,Z](8)[A,B,C,E,Z,G,F]DFA这状态图如下：确定有限自动机图如下：（3）将DFA最小化：先将终态和非终态分成两个集:K1={1,2,3,4},K2={5,6,7,8}对于K1中的3态输入a则进入K2集，而1，2，4态输入a仍然在K1中，故K1可一分为二K11={1,2,4}和K12={3};考察K11对于1，4态输入b到达3态而2态输入b到达4态。故K11可一分为二K111={1,4};K112={2}最后考察K2输入a或b都到达K2集。则DFA化简为{1，4}，{2}，{3}，{5，6，7，8}四个子集。其状态图如下：