编译原理陈意云_课后答案1.ppt

编译原理习题课(1),栾俊luanj12/13/2019,2019/12/13,luanj,2,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)*)*,2019/12/13,luanj,3,2.3(续),一种表述(这里说的01串包括)0(0|1)*0以0开头和结尾的长度至少是2的01串(|0)1*)*所有的01串(0|1)*0(0|1)(0|1)倒数第三位是0的01串0*10*10*10*含有3个1的01串(00|11)*(01|10)(00|11)*(01|10)(00|11)*)*含有偶数个0和偶数个1的01串(习题集P1/1.1),2019/12/13,luanj,4,2.4,为下列语言写正规定义包含5个元音的所有字母串，其中每个元音只出现一次且按序排列按词典序排列的所有字母串C语言的注释相邻数字都不相同的所有数字串最多只有一处相邻数字相同的所有数字串由偶数个0和偶数个1组成的所有01串由偶数个0和奇数个1组成的所有01串不含字串011的01串,2019/12/13,luanj,5,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语言的注释不含/，*的任意字符记为不含*/的任意字符串:(*+/*)*/*(*+/*)*/,2019/12/13,luanj,6,2.4(续),一种答案(续)相邻数字都不相同的所有数字串123031357106678035123031357106678035313571答案见习题集P2/1.3,2019/12/13,luanj,7,2.4(续),一种答案(续)最多只有一处相邻数字相同的所有数字串与上题类似12303135710066780351230313571006678035313571answer-double_0|double_1|double_9其中double_i表示相邻的数字是idouble_0-0?(no_00)*no_000(no_00)*no_0?|00no_0-,2019/12/13,luanj,8,2.4(续),一种答案(续)最多只有一处相邻数字相同的所有数字串(续)double_i-i?(no_ii)*no_iii(no_ii)*no_i?|iino_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?|55no_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_5no_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-,2019/12/13,luanj,9,2.4(续),一种答案(续)由偶数个0和偶数个1组成的所有01串习题集P2/1.2由偶数个0和奇数个1组成的所有01串习题集P2/1.2,2019/12/13,luanj,10,2.4(续),一种答案(续)不含字串011的01串当出现0后，1只能单独出现1*(0+1)*0*,2019/12/13,11,可编辑,2019/12/13,luanj,12,2.7,用算法2.4为下列正规式构造NFA，并给出处理ababbab的状态转换序列(a|b)*(a*|b*)*(|a)b*)*(a|b)*abb(a|b)*,2019/12/13,luanj,13,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-f,2019/12/13,luanj,14,2.11,可以通过正规式的最简DFA同构来证明正规式等价。证明下列正规式等价(a|b)*(a*|b*)*(|a)b*)*,2019/12/13,luanj,15,2.11(续),NFA-DFA,-closure(s)=s,4,f,0,2,3,5,6,8=A-closure(move(A,a)=-closure(1)=1,5,6,8,4,f,0,2,3=B-closure(move(A,b)=-closure(7)=7,6,8,4,f,0,2,3,5=C-closure(move(B,a)=-closure(1)=B-closure(move(B,b)=-closure(7)=C-closure(move(C,a)=-closure(1)=B-closure(move(C,b)=-closure(7)=C,2019/12/13,luanj,16,2.11(续),DFA-最简DFA,b,划分为接受状态集合F=A,B,C和非接受状态S-F=由于S-F为空集，只考虑F：对于A，输入a，转换为B，输入b，转换为C对于B，输入a，转换为B，输入b，转换为C对于C，输入a，转换为B，输入b，转换为C因此F不需进一步划分,