《编译第二章习题解答》由会员分享，可在线阅读，更多相关《编译第二章习题解答（22页珍藏版）》请在金锄头文库上搜索。
1、第三章 词法分析,习题,给一个语言（或者给一个正则表达式） 给出该语言的正规式（或者根据已知的正则表达式写出该语言的含义）（3分） 画出接收该语言的NFA（4分） 把该NFA转换成等价的DFA（4分） 对该DFA进行状态最小化（4分）,题目类型：,7. 构造下列正规式的DFA,7.1 1(0|1)*101,以1打头，以101结尾的所有由0和1组成的符号串。,确定化,最小化,I=I(1)，I(2)= 4, 0,1,2,3 ,解. 初始划分:,0:,I(1)不能再被细分，考察I(2)=0,1,2,3,0,1,2,30=1,2,3,落入了0,1,2,3,0,1,2,31=1,2,落入了0,1,2,3
2、,I(2) 不能再被细分。所以，最小化后的DFA如上图所示。,7.2 1(1010*|1(010)*1)*0,以1打头，以0结尾的。所有由0和1组成的符号串。,8. 给出下面正规表达式,(8.1) 以01结尾的二进制数串:(0|1)*01,(8.2)能被5整除的十进制整数非0打头,n = (1|2|3|9)+(0|5),(8.3) 包含 奇数个0 或 奇数个1的二进制数串,奇数个1：r1= 0*1(0|10*1)* 奇数个0：r2=1*0(1|01*0)* r=r1|r2,(8.4) 英文字母 组成的所有符号串, 要求符号串中的字母依照字典序 排列,(a|A)*(b|B)*(z|Z)*,令：
3、ri=i|，i=0,1,2,9 P(0,1,2,9)表示0,1,2,9的全体排列 则：r=P(r0,r1,r9),(8.5) 没有重复出现的数字 的数字符号串的全体,(8.6) 最多有一个重复出现的数字 的数字符号串的全体,令： ri=i|，i=0,1,2,9 s=0|1|2|9| P(0,1,2,9)表示0,1,2,9的全体排列 则：r=P(r0,r1,r9,s),(8.7) 不包含子串abb 的由a和b组成的符号串的全体,b*(a|ab)*,最小化？,9. 给出DFA及正规表达式,(9.1) 0,1 上的含有子串010的所有串,(0|1)*010(0|1)*,确定化,0 1 2 3,4,5
4、,最小化,(9.2) 0,1 上的 不含子串010的所有串,1*(0|111*)*1*,确定化,0,1,2,3,4,5,6 0,2,4,5,6 1 3,最小化,补充: 所有不含子串011的01串,1*(01|0)*,10. 狼, 山羊, 白菜,M : 人 W: 狼 S: 羊 C: 白菜,状态中间的横线代表河, 横线上下两侧字母分别表示北岸和南岸现有的人或物, 弧线上的字母表示正在过河的人和物,M : 人 W: 狼 S: 羊 C: 白菜,状态中间的横线代表河, 横线上下两侧字母分别表示北岸和南岸现有的人或物, 弧线上的字母表示正在过河的人和物,(12.a) 确定化和最小化,最小化结果,确定化结果,(12.b) 确定化和最小化,最小化,0: 0,1 2,3,4,5 1: 0,1 2,4 3,5,14. 构造DFA, 它接受=0,1上所有满足如下条件的字符串: 每个1都有0直接跟在右边,确定化,最小化,
