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

1、编译原理习题课(1),栾 俊 9/20/2020,2020/9/20,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)*)*,2020/9/20,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|1

2、0)(00|11)*)*含有偶数个0和偶数个1的01串(习题集P1/1.1),2020/9/20,4,2.4,为下列语言写正规定义 包含5个元音的所有字母串，其中每个元音只出现一次且按序排列 按词典序排列的所有字母串 C语言的注释 相邻数字都不相同的所有数字串 最多只有一处相邻数字相同的所有数字串 由偶数个0和偶数个1组成的所有01串 由偶数个0和奇数个1组成的所有01串 不含字串011的01串,2020/9/20,5,2.4 (续),一种答案 包含5个元音的所有字母串，其中每个元音只出现一次且按序排列 5个元音a, e, i, o, u 不含5个元音的任意字符：B-DF-HJ-NP-TV-Z

3、b-df-hj-np-tv-z，记为 *(a|A)*(e|E)*(i|I)*(o|O)*(u|U)* 按词典序排列的所有字母串 A*a*B*b*Z*z* C语言的注释 不含/，*的任意字符记为 不含*/的任意字符串: (*+/*)* /*(*+/*)*/,2020/9/20,6,2.4 (续),一种答案(续) 相邻数字都不相同的所有数字串 123031357106678035123 0 313571 0 6678 0 353 1 357 1 答案见习题集P2/1.3,2020/9/20,7,2.4 (续),一种答案(续) 最多只有一处相邻数字相同的所有数字串 与上题类似123031357100

4、6678035123 0 313571 00 6678 0 353 1 357 1 answer-double_0|double_1|double_9其中double_i表示相邻的数字是i double_0 - 0?(no_00)*no_000(no_00)*no_0?|00no_0 - ,2020/9/20,8,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

5、-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)

6、*(no_0-5?)|no_0-5no_0-5-,2020/9/20,9,2.4 (续),一种答案(续) 由偶数个0和偶数个1组成的所有01串 习题集P2/1.2 由偶数个0和奇数个1组成的所有01串 习题集P2/1.2,2020/9/20,10,2.4 (续),一种答案(续) 不含字串011的01串 当出现0后，1只能单独出现 1*(0+1)*0*,2020/9/20,11,2.7,用算法2.4为下列正规式构造NFA，并给出处理ababbab的状态转换序列 (a|b)* (a*|b*)* (|a)b*)* (a|b)*abb(a|b)*,2020/9/20,12,2.7 (续),(|a)b*

7、)*,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,2020/9/20,13,2.11,可以通过正规式的最简DFA同构来证明正规式等价。证明下列正规式等价 (a|b)* (a*|b*)* (|a)b*)*,2020/9/20,14,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,2020/9/20,15,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