编译原理陈意云课后答案PPT课件市公开课一等奖百校联赛获奖课件.pptx

编译原理习题课编译原理习题课(1)栾 俊10/10/10/10/第1页2.3叙述由以下正规式描述语言0(0|1)*0(|0)1*)*(0|1)*0(0|1)(0|1)0*10*10*10*(00|11)*(01|10)(00|11)*(01|10)(00|11)*)*10/10/第2页2.3(续续)一个表述(这里说01串包含)0(0|1)*0以0开头和结尾长度最少是201串(|0)1*)*全部01串(0|1)*0(0|1)(0|1)倒数第三位是001串0*10*10*10*含有3个101串(00|11)*(01|10)(00|11)*(01|10)(00|11)*)*含有偶数个0和偶数个101串(习题集P1/1.1)10/10/第3页2.4为以下语言写正要求义包含5个元音全部字母串，其中每个元音只出现一次且按序排列按词典序排列全部字母串C语言注释相邻数字都不相同全部数字串最多只有一处相邻数字相同全部数字串由偶数个0和偶数个1组成全部01串由偶数个0和奇数个1组成全部01串不含字串01101串10/10/第4页2.4(续续)一个答案包含5个元音全部字母串，其中每个元音只出现一次且按序排列5个元音a,e,i,o,u 不含5个元音任意字符：B-DF-HJ-NP-TV-Zb-df-hj-np-tv-z，记为*(a|A)*(e|E)*(i|I)*(o|O)*(u|U)*按词典序排列全部字母串A*a*B*b*Z*z*C语言注释不含/，*任意字符记为不含*/任意字符串:(*+/*)*/*(*+/*)*/10/10/第5页2.4(续续)一个答案(续)相邻数字都不相同全部数字串123031357106678035123 0 313571 0 6678 0 353 1 357 1 答案见习题集P2/1.310/10/第6页2.4(续续)一个答案(续)最多只有一处相邻数字相同全部数字串与上题类似1230313571006678035123 0 313571 00 6678 0 353 1 357 1 answer-double_0|double_1|double_9其中double_i表示相邻数字是idouble_0-0?(no_00)*no_000(no_00)*no_0?|00no_0 -10/10/第7页2.4(续续)一个答案(续)最多只有一处相邻数字相同全部数字串(续)double_i -i?(no_ii)*no_iii(no_ii)*no_i?|ii no_i -(0|no_0_i0)(no_0_i0)*(no_0_i?)|no_0_ino_0_i -no_0-(i-2)_i-no_0-(i+1)-比如i=5double_5 -5?(no_55)*no_555(no_55)*no_5?|55 no_5 -0|no_0_50)(no_0_50)*(no_0_5?)|no_0_5no_0_5-1|no_0-1_51)(no_0-1_51)*(no_0-1_5?)|no_0-1_5 no_0-1_5-2|no_0-2_52)(no_0-2_52)*(no_0-2_5?)|no_0-2_5no_0-2_5-3|no_0-3_53)(no_0-3_53)*(no_0-3_5?)|no_0-3_5no_0-3_5-4|no_0-54)(no_0-54)*(no_0-5?)|no_0-5no_0-5-10/10/第8页2.4(续续)一个答案(续)由偶数个0和偶数个1组成全部01串习题集P2/1.2由偶数个0和奇数个1组成全部01串习题集P2/1.210/10/第9页2.4(续续)一个答案(续)不含字串01101串当出现0后，1只能单独出现1*(0+1)*0*10/10/第10页2.7用算法2.4为以下正规式结构NFA，并给出处理ababbab状态转换序列(a|b)*(a*|b*)*(|a)b*)*(a|b)*abb(a|b)*10/10/第11页2.7(续续)(|a)b*)*ababbab:s-4-0-1-5-6-7-8-4-0-1-5-6-7-6-7-8-4-0-1-5-6-7-8-f01a234567b58sfstart10/10/第12页2.11能够经过正规式最简DFA同构来证实正规式等价。证实以下正规式等价(a|b)*(a*|b*)*(|a)b*)*10/10/第13页2.11(续续)NFA-DFA1)-closure(s)=s,4,f,0,2,3,5,6,8=A2)-closure(move(A,a)=-closure(1)=1,5,6,8,4,f,0,2,3=B3)-closure(move(A,b)=-closure(7)=7,6,8,4,f,0,2,3,5=C4)-closure(move(B,a)=-closure(1)=B5)-closure(move(B,b)=-closure(7)=C6)-closure(move(C,a)=-closure(1)=B7)-closure(move(C,b)=-closure(7)=Cbab abstartCBAa10/10/第14页2.11(续续)DFA-最简DFAb1)划分为接收状态集合F=A,B,C和非接收状态S-F=2)因为S-F为空集，只考虑F：对于A，输入a，转换为B，输入b，转换为C 对于B，输入a，转换为B，输入b，转换为C 对于C，输入a，转换为B，输入b，转换为C 所以F不需深入划分sstartab10/10/第15页2.13结构表示0，1个数都是偶数01字符串DFA习题集P3/1.410/10/第16页2.14能被5整除二进制数习题集P4/1.510/10/第17页谢谢！谢谢！10/10/第18页