资源描述：
《编译原理(龙书)答案第三章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、3.3.2,3.3.6,3.3.7,3.3.8,3.3.9,3.6.3,3.6.4,3.6.53.7.1,3.7.2,3.7.33.8.1,3.8.23.9.33.3.2描述下列正则表达式代表的语言。a)a(a
2、b)*ab)((ε
3、a)b*)*c)(a
4、b)*a(a
5、b)(a
6、b)d)a*ba*ba*ba*e)(aa
7、bb)*((ab
8、ba)(aa
9、bb)*(ab
10、ba)(aa
11、bb)*)*答案(a)由a开头并结尾的由a和b构成的字符串(b)由a和b构成的字符串(c)倒数第三位为a的由a和b构成的
12、字符串(d)仅含3个b的由a和b构成的字符串(e)含有偶数个a和偶数个b的由a和b构成的字符串注意：请准确描述语言的性质而不是列举满足正则表达式的串3.3.6写出满足下列定义的字符a)Thefirsttenlettersineitherupperorlowercaseb)Thelowercaseconsonantsc)The“digits”inahexadecimalnumberd)ThecharactersthatcanappearattheendofalegitimateEnglishsent
13、ence答案(a)a-jA-J(b)a-j(c)0-9a-f(d).?!3.3.7写出匹配字符串“的正则表达式答案：”\3.6.3对于图3.29表示的NFA,列出aabb的所有路径。这个NFA能否接受aabb?答案：aabb的所有路径012230011101200000000012220001100123存在路径1223和0123所以能接受aabb3.6.4对于图3.30表示的NFA,列出aabb的所有路径。这个NFA能否接受aabb?答案：0101230101212030123030121
14、2030303232030303212303030321212由于存在03210这样的环,所以这里有无数种路径存在路径终止于3,所以能接受aabb3.6.5给出以下NFA的TransitionTable(a)图3.29(b)图3.30(c)图3.26答案:(a)Stateabe0{0,1}{0}空集1{1,2}{1}空集2{2}{2,3}{0}3空集空集空集(b)Stateabe0{1}空集{3}1空集{2}{0}2空集{3}{1}3{0}空集{2}(c)Stateabe0空集空集{1,3}1{2
15、}空集空集2{2}空集空集3空集{4}空集4空集{4}空集3.7.1把下列NFA转化为DFA(a)图3.26(b)图3.29(c)图3.30答案:(a)(b)(c)a,bA注意:以上答案并不唯一,等价即可3.7.2用算法3.22模拟NFA(输入为aabb)(a)图3.29(b)图3.30答案:(a)SnextChar{0}a{0,1}a{0,1,2}b{0,1,2,3}b{0,1,2,3}eofF={3}所以返回yes(b)SnextChar{0,1,2,3}a{0,1,2,3}a{0,1,2,3
16、}b{0,1,2,3}b{0,1,2,3}eofF={3},所以返回yes3.7.3用算法3.23和3.20把下列正则表达式转换为DFAa)(alb)*b)(a*lb*)*c)((ela)b*)*d)(alb)*abb(alb)*答案：a)NFADFANFAStateDFAStateab{0,1,2,3,7}ABC{1,2,3,4,6,7}BBC{1,2,3,5,6,7}CBCb)NFADFANFAStateDFAStateab{0,1,2,3,4,5,8,9,10,11}ABC{1,2,3,4,
17、5,6,8,9,10,11}BBC{1,2,3,4,5,7,8,9,10,11}CBCc)NFADFANFAStateDFAStateab{0,1,2,3,4,6,7,9,10}ABC{1,2,3,4,5,6,7,9,10}BBC{1,2,3,4,6,7,8,9,10}CBCd)NFADFANFAStateDFAStateab{0,1,2,3,7}ABC{1,2,3,4,6,7,8}BBD{1,2,3,5,6,7}CBC{1,2,3,5,6,7,9}DBE{1,2,3,5,6,7,10,11,12
18、,13,17}EFG{1,2,3,4,6,7,8,11,12,13,14,16,17}FFG{1,2,3,5,6,7,11,12,13,15,16,17}GFG注意：这道题要求大家按照算法构造NFA和DFA，有些同学的NFA没有完全按照算法构造。另外，画NFA和DFA时务必标出开始状态和终止状态。3.8.1NFADFA3.8.2与3.8.1类似，请耐心构造相应的NFA和DFA3.8.3这3个正则表达式对应的最小DFA都与如下的DFA同构，所以它们等价。
