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|b)*ab)((ε|a)b*)*c)(a|b)*a(a|b)(a|b)d)a*ba*ba*ba*e)(aa|bb)*((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*)*答案(a)由a开头并结尾的由a和b构成的字符串(b)由a和b构成的字符串(c)倒数第三位为a的由a和b构成的字符串(d)仅含3个b的由a和b构成的字符串(e)含有偶数个a和偶数个b的由a和b构成的字符串注意：请准确描述语言的性质而不是列举满足正则表达式的串3.3.6写出满足下列定义的字符a)Thefirsttenlettersineitherupperorlowercaseb)Thelowercaseconsonantsc)The“digits”inahexadecimalnumberd)ThecharactersthatcanappearattheendofalegitimateEnglishsentence答案(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?答案：01012301012120301230301212030303232030303212303030321212由于存在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}空集空集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}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,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,13,17}EFG{1,2,3,4,6,7,8,11,12,13,14,16,17}FFG{1,2,3,