编译原理陈意云-课后答案1课件

编译原理习题课(1)12/21/202212/21/202212.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/21/202222.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)

12/21/202232.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/21/202252.4(续)一种答案(续)相邻数字都不相同的所有数字串1230335

1230

313571

06678035

313571答案见习题集P2/1.312/21/202262.4(续)一种答案(续)最多只有一处相邻数字相同的所有数字串与上题类似

12303035

1230

313571

006678035

313571answer->double_0|double_1|…|double_9

其中double_i表示相邻的数字是idouble_0->0?(no_00)*no_000(no_00)*no_0?|00

no_0->…

…12/21/202272.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_i

no_0_i->…

…

no_0-(i-2)_i->…

no_0-(i+1)->…

…比如i=5

double_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_5

no_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_5

no_0-2_5->3|no_0-3_53)(no_0-3_53)*(no_0-3_5?)|no_0-3_5

no_0-3_5->4|no_0-54)(no_0-54)*(no_0-5?)|no_0-5

no_0-5->…

…12/21/202282.4(续)一种答案(续)不含字串011的01串当出现0后，1只能单独出现1*(0+1)*0*12/21/2022102.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εε01a23ε45εεεεεε67b58εsfεεεstart12/21/2022122.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})=CbababstartCBAa12/21/2022142.11(续)DFA->最简DFAb划分为接受状态集合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不需进一步划分sstar