编译课后答案课件-陈火旺等编著第三版

编译课后答案课件编译课后答案课件-陈火陈火旺等编著第三版旺等编著第三版2CH.3.CH.3.练习题练习题2(2(P63.)P63.)n2.2.给出下面给出下面C+C+程序段中的单词符号及其属性值。程序段中的单词符号及其属性值。int CInt:nMulDiv(int n1,int n2)int CInt:nMulDiv(int n1,int n2)if(n3=0)return 0;if(n3=0)return 0;else return(n1*n2)/n3;else return(n1*n2)/n3;n问题问题：没写全；表达不准确：没写全；表达不准确n解解：,2024/5/3作业评讲3CH.3.CH.3.练习题练习题2(2(P63.)P63.)n续解续解：,。2024/5/3作业评讲4CH.3.CH.3.练习题练习题5(5(P63.)P63.)n5.5.证明证明3.3.13.3.1中关于正规式的交换律、结合中关于正规式的交换律、结合律等五个关系。律等五个关系。n解：解：证明证明 U|V=V|U 因为因为 L(U|V)=L(U)L(V)=L(V)L(U)=L(V|U)n解：解：证明证明 U(VW)=(UV)W 因为因为 L(U(VW)=L(U)L(VW)=L(U)(L(V)L(W)=(L(U)L(V)L(W)=L(UV)L(W)=L(UV)W)5CH.3.CH.3.练习题练习题7(7(P64.)P64.)n7.7.问题问题：没构造出：没构造出DFADFA；没过程；方法没掌握；没过程；方法没掌握。(1)1(0|1)*101 解解1:正规式对应的正规式对应的NFA:XY34511011210 I I0 I1X 1,3,2 1,3,2 3,2 3,4,2 3,2 3,2 3,4,2 3,4,2 3,5,2 3,4,2 3,5,2 3,2 3,Y,4,23,Y,4,23,5,2 3,4,2 I I0 I1初初0 1 1 2 3 2 2 3 3 4 3 4 2 5终终5 4 3CH.3.CH.3.练习题练习题7(7(P64.)P64.)(1)正规式正规式 1(0|1)*101DFA:初始初始:0,1,2,3,4和和50,1,2,3,40=2,4 0,1,2,3,41=1,3,5划分为划分为0,1,2,3和和40,1,2,30=2,4划分为划分为0,1,2和和30,1,21=1,3划分为划分为0和和1,21,20=2 1,21=3最后划分得最后划分得5个子集个子集:0,1,2,3,4,5105341101101010最小化最小化DFA:1053411011201001017CH.3.CH.3.练习题练习题7(7(P64.)P64.)n7.7.构造下列正规式相应的构造下列正规式相应的DFADFA。(1)1(0|1)*101 解解2:正规式对应的正规式对应的NFA:04123110110 I I0 I10 初初01 11 11 11,2 21,2 21,3 31,2 21,3 31 11,2,4 41,2,4终终4 1,3 31,2 210423110110010DFA:8CH.3.CH.3.练习题练习题7(7(P64.)P64.)(3)正规式正规式 0*10*10*10*DFA:最小化最小化DFA:107340100120110101560010601200104NFA:111001400107X325698Y9CH.3.CH.3.练习题练习题8(8(P64.)P64.)n8.8.给出下面的正规表达式给出下面的正规表达式。(1)以以01结尾的二进制数串结尾的二进制数串;正规式正规式 (0|1)*01 或或(0*1*)*01(2)能被能被5整除的十进制整数整除的十进制整数;正规式正规式：(0|1|2|3|4|5|6|7|8|9)*(0|5)或或(0*1*2*3*4*5*6*7*8*9*)*(0|5)或或(0|5)|(1|2|3|9)(0|1|2|3|9)*(0|5)(3)英文字母组成的所有符号串英文字母组成的所有符号串,要求符号串中的字要求符号串中的字母依照字典序排列母依照字典序排列;正规式正规式 (a|A)*(b|B)*(c|C)*(d|D)*(z|Z)*2024/5/3作业评讲10CH.3.CH.3.练习题练习题9(9(P64.)P64.)n9.9.问题问题：没构造出：没构造出DFADFA；没过程；方法没掌握；没过程；方法没掌握。(1)0,1上的含有子串上的含有子串010的所有串的所有串;至少含一个。至少含一个。正规式正规式 (0|1)*010(0|1)*或或 (0*1*)*010(0*1*)*NFA:1AD0B0,100,1C I I0 I1A 初初 0A,B 1 A 0A,B 1A,B 1A,C 2A,C 2A,B,D 3A 0 A,B,D 终终3A,B,D 3A,C,D 4A,C,D 终终4A,B,D 3A,D 5A,D 终终5 A,B,D 3A,D 511CH.3.CH.3.练习题练习题9(9(P64.)P64.)n 正规式正规式 (0|1)*010(0|1)*最小化最小化DFA:1030011100,12DFA:1050011101230400112024/5/3作业评讲12CH.3.CH.3.练习题练习题10(10(P64.)P64.)n10.10.用用FAFA写出渡河的方法。写出渡河的方法。n设：人设：人-R R；狼狼-L L；羊羊-Y Y；菜菜-C C；左岸左岸-Z Z；右岸右岸-U;U;状态状态 左岸到右岸左岸到右岸,人或人带一件东西人或人带一件东西 右岸到左岸右岸到左岸,人或人带一件东西人或人带一件东西左左:右右:+人人,东西东西人人,东西东西2024/5/3作业评讲13CH.3.CH.3.练习题练习题10(10(P64.)P64.)Z:U:rlyc+r,crZ:cU:rlyZ:rycU:l+r,lZ:lcU:ry+r,yZ:rlcU:y+r,lZ:yU:rlcZ:ryU:lcZ:rlycU:Z:lU:rycZ:rlyU:cr,yr,y+r,cr+r,y2024/5/3作业评讲14CH.3.CH.3.练习题练习题12(12(P64.)P64.)n12.12.问题问题：没过程；方法没掌握：没过程；方法没掌握。n将将(a)a)确定化。确定化。I Ia Ib0 初终初终0 0,1 1 1 2 0,1 终终1 0,1 1 1 2 1 2 0 0 0a1a,ba0a2aa最小化最小化DFA:1bb0a2ba确定化确定化DFA:确定化确定化:(a)NFA:15CH.3.CH.3.练习题练习题12(12(P64.)P64.)n12.12.将将(b)b)最小化。最小化。(b)DFA:初始初始:0,1,2,3,4,5 0,1a=1 0,1b=2,4 不分不分 2,3,4,5a=1,3,0,5分成分成 2,4和和3,5 2,4a=1,0 2,4b=3,5 不分不分 3,5a=3,5 3,5b=2,4 不分不分最后得到三个子集最后得到三个子集:0,1,2,4,3,5选出代表选出代表:0,2,3最小化的结果如图所示最小化的结果如图所示0a2baaabbbabb31a45302ababab最小化最小化DFA:16CH.3.CH.3.练习题练习题14(14(P64.)P64.)n14.14.问题问题：没构造出：没构造出DFADFA；没过程；方法没掌握；没过程；方法没掌握。(1)正规式正规式:(10|0)*(2)NFA:确定化确定化:YX1001201001012 I I0 I1X,1,Y 1,Y2 1,Y1,Y2 21,Y I I0 I1初终初终0 1 2 终终 1 1 2 2 1 DFA:17CH.3.CH.3.练习题练习题15(15(P64.)P64.)n15.15.问题问题：没转换过程；转换方法没掌握：没转换过程；转换方法没掌握。S0S|1S|1A|0B A1C|1 B0C|0 C0C|1C|0|1GRFA:fC0,11001010SA0,11BFA GL:fA1|B0|C1|C0 AS1|1 BS0|0 CA1|B0|C1|C0 SS0|S1|1|0