资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,*,*,编译原理习题课,(1),栾 俊,11/16/2024,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)*)*,11/16/2024,2,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),11/16/2024,3,2.4,为下列语言写正规定义,包含,5,个元音的所有字母串，其中每个元音只出现一次且按序排列,按词典序排列的所有字母串,C,语言的注释,相邻数字都不相同的所有数字串,最多只有一处相邻数字相同的所有数字串,由偶数个,0,和偶数个,1,组成的所有,01,串,由偶数个,0,和奇数个,1,组成的所有,01,串,不含字串,011,的,01,串,11/16/2024,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,语言的注释,不含,/,，*的任意字符记为,不含,*,/,的任意字符串,:(*,*,+,/,*,),*,/*(*,*,+,/,*,),*,*/,11/16/2024,5,2.4(,续,),一种答案,(,续,),相邻数字都不相同的所有数字串,123031357106678035123,0,313571,0,6678,0,353,1,357,1,答案见习题集,P2/1.3,11/16/2024,6,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,-,11/16/2024,7,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,-,11/16/2024,8,2.4(,续,),一种答案,(,续,),由偶数个,0,和偶数个,1,组成的所有,01,串,习题集,P2/1.2,由偶数个,0,和奇数个,1,组成的所有,01,串,习题集,P2/1.2,11/16/2024,9,2.4(,续,),一种答案,(,续,),不含字串,011,的,01,串,当出现,0,后，,1,只能单独出现,1*(0,+,1)*0*,11/16/2024,10,2.7,用算法,2.4,为下列正规式构造,NFA,，并给出处理,ababbab,的状态转换序列,(,a|b,)*,(a*|b*)*,(,|,a,)b,*)*,(,a|b,)*,abb(a|b,)*,11/16/2024,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-f,0,1,a,2,3,4,5,6,7,b,5,8,s,f,start,11/16/2024,12,2.11,可以通过正规式的最简,DFA,同构来证明正规式等价。证明下列正规式等价,(,a|b,)*,(a*|b*)*,(,|,a,)b,*)*,11/16/2024,13,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,11/16/2024,14,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,11/16/2024,15,2.13,构造表示,0,，,1,个数都是偶数的,01,字符串的,DFA,习题集,P3/1.4,11/16/2024,16,2.14,能被,5,整除的二进制数,习题集,P4/1.5,11/16/2024,17,谢谢！,
展开阅读全文