编译原理陈意云课后答案优质课件专业知识讲座.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,*,luanj,*,本文档所提供的信息仅供参考之用，不能作为科学依据，请勿模仿。文档如有不当之处，请联系本人或网站删除。,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)*)*,12/12/2025,1,luanj,2.3(续),一种表述(这里说的01串包括,),0(0|1)*0以0开头和结尾的,长度至少是2,的01串,(,|0)1*)*所有的01串,(0|1)*0(01)(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),12/12/2025,2,luanj,2.4,为下列语言写正规定义,包含5个元音的所有字母串，其中每个元音只出现一次且按序排列,按词典序排列的所有字母串,C语言的注释,相邻数字都不相同的所有数字串,最多只有一处相邻数字相同的所有数字串,由偶数个0和偶数个1组成的所有01串,由偶数个0和奇数个1组成的所有01串,不含字串011的01串,12/12/2025,3,luanj,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语言的注释,不含/，*的任意字符记为,不含*/的任意字符串:(*,*,+,/,*,),*,/*(*,*,+,/,*,),*,*/,12/12/2025,4,luanj,2.4(续),一种答案(续),相邻数字都不相同的所有数字串,123031357106678035123,0,3135710,6678,0,353,1,357,1,答案见习题集P2/1.3,12/12/2025,5,luanj,2.4(续),一种答案(续),最多只有一处相邻数字相同的所有数字串,与上题类似1230313571006678035123,0,313571,00,6678,0,353,1,357,1,answer,-,double_0,|,double_1,|,double_9,其中double_i表示相邻的数字是i,double_0,-0?(,no_0,0)*,no_0,00(,no_0,0)*,no_0,?|00,no_0,-,12/12/2025,6,luanj,2.4(续),一种答案(续),最多只有一处相邻数字相同的所有数字串(续),double_i,-i?(,no_i,i)*,no_i,ii(,no_i,i)*,no_i,?|ii,no_i,-(0|,no_0_i,0)(,no_0_i,0)*(,no_0_i,?)|,no_0_ino_0_i,-,no_0-(i-2)_i,-,no_0-(i+1),-,比如i=5,double_5,-5?(,no_5,5)*,no_5,55(,no_5,5)*,no_5,?|55,no_5,-0|,no_0_5,0)(,no_0_5,0)*(,no_0_5,?)|,no_0_5no_0_5,-1|,no_0-1_5,1)(,no_0-1_5,1)no_0-1_5,?)|,no_0-1_5,no_0-1_5,-2|,no_0-2_5,2)(,no_0-2_5,2)*(,no_0-2_5,?)|,no_0-2_5,no_0-2_5,-3|,no_0-3_5,3)(,no_0-3_5,3)*(,no_0-3_5,?)|,no_0-3_5,no_0-3_5,-4|,no_0-5,4)(,no_0-5,4)*(,no_0-5,?)|,no_0-5,no_0-5,-,12/12/2025,7,luanj,2.4(续),一种答案(续),由偶数个0和偶数个1组成的所有01串,习题集P2/1.2,由偶数个0和奇数个1组成的所有01串,习题集P2/1.2,12/12/2025,8,luanj,2.4(续),一种答案(续),不含字串011的01串,当出现0后，1只能单独出现,1*(0,+,1)*0*,12/12/2025,9,luanj,2.7,用算法2.4为下列正规式构造NFA，并给出处理ababbab的状态转换序列,(a|b)*,(a*|b*)*,(,|a,)b*)*,(a|b)*abb(a|b)*,12/12/2025,10,luanj,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,0,1,a,2,3,4,5,6,7,b,5,8s,f,start,12/12/2025,11,luanj,2.11,可以通过正规式的最简DFA同构来证明正规式等价。证明下列正规式等价,(a|b)*,(a*|b*)*,(,|a,)b*)*,12/12/2025,12,luanj,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,b,a,b,a,b,start,C,B,A,a,12/12/2025,13,luanj,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,不需进一步划分,s,start,a,b,12/12/2025,14,luanj,2.13,构造表示0，1个数都是偶数的01字符串的DFA,习题集P3/1.4,12/12/2025,15,luanj,2.14,能被5整除的二进制数,习题集P4/1.5,12/12/2025,16,luanj,谢谢！,12/12/2025,17,luanj,