资源描述:
《编译原理第2章习题课.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、1.构造正规式的DFA。(1)1(0
2、1)*1010YXCADBE首先构造NFA:ε0X11Eε1DCBA1NFA化为DFA:状态转换表:Q10{X}A{ABC}B{ABC}B{BCD}C{BC}D{BCD}C{BCD}C{BCE}E{BC}D{BCD}C{BC}D{BCE}E{BCDY}Y{BC}D{BCDY}Y{BCD}C{BCE}E1状态转换图:0110110YABCDE10初态010ABBCDCCEDCDEYDYCE化简后得:01ABEY1101001C(2)(a
3、b)*(aa
4、bb)(a
5、b)*X12345Yεεaaεbbabab?NFA化为DFA:Qab{X12}
6、{123}{124}{123}{1235Y}{124}{124}{123}{1245Y}{1235Y}{1235Y}{124Y}{1245Y}{123Y}{1245Y}{124Y}{123Y}{1245Y}{123Y}{1235Y}{124Y}a所以,DFA为:X123456ababbabbabaab化简得:1XY2baababab0εε1BCDYεXAε10(3)(0
7、11*0)*NFA到DFA:Q10{XAY}X{BCD}A{AY}B{BCD}A{CD}Y{AY}B{AY}B{BCD}A{AY}B{CD}Y{CD}Y{AY}BABYX10100110化简后得;XA1001
8、2.将下图确定化和最小化。aaÞ01a,b解:首先取A=ε-CLOSURE({0})={0},NFA确定化后的状态矩阵为:Q’abA{0}{0,1}{1}B{0,1}{0,1}{1}C{1}{0}NFA确定化后的DFA为:aaÞABabbC将A,B合并得:abÞACa3.构造一个DFA,它接受∑={0,1}上所有满足如下条件的字符串,每个1都有0直接跟在后边。解:按题意相应的正规表达式是0*(0
9、10)*0*构造相应的DFA,首先构造NFA为000310XεεεεY102用子集法确定化II0I1S01{X,0,1,3,Y}{0,1,3,Y}{2}{1,3,Y}{0,1,3,Y
10、}{0,1,3,Y}{1,3,Y}{1,3,Y}{2}{2}/{2}12342244333DFA为010211013404.给出NFA等价的正规式R。方法一:首先将状态图转化为BYCBAXε11ε消去得0,1εYCAX11ε消去其余结点、0,1YX(0
11、1)*11NFA等价的正规式为(0
12、1)*11方法二:NFA→右线性文法→正规式A→0A
13、1A
14、1BB→1CC→εA=0A+1A+1BB=1A=0A+1A+11A=(0+1)*11→(0
15、1)*115.试证明正规式(a
16、b)*与正规式(a*
17、b*)*是等价的。a证明:(1)Y1X正规式(a
18、b)*的NFA为=>εεbab{X,
19、1,y}{1,y}{1,y}{1,y}{1,y}{1,y}aA其最简DFA为=>b(2)正规式(a*
20、b*)*的NFA为:3a其最简化DFA为:aAεε2Y1=>Xεε=>εεbbDFA的状态转换表:ab{x,1,2,3,y}{1,2,3,y}{1,2,3,y}{1,2,3,y}{1,2,3,y}{1,2,3,y}由于这两个正规式的最小DFA相同,所以正规式(a
21、b)*等价于正规式(a*
22、b*)*。6.设字母表∑={a,b},给出∑上的正规式R=b*ab(b
23、ab)*。(1)试构造状态最小化的DFAM,使得L(M)=L(R)。(2)求右线性文法G,使L(G)=L(M)。解:(
24、1)构造NFA:X123Yεεbab45εε6abb(2)将其化为DFA,转换矩阵为:Qab{X,1,2}1{3}2{1,2}3{3}2{4,5,Y}4{1,2}3{3}2{1,2}3{4,5,Y}4{6}5{5,Y}6{6}5{5,Y}6{5,Y}6{6}5{5,Y}6123456abbababbba再将其最小化得:XWYabbab(2)对应的右线性文法G=({X,W,Y},{a,b},P,X)P:X→aW
25、bXW→bY
26、by→aW
27、bY
28、b3.8文法G[〈单词〉]为:〈单词〉-〉〈标识符〉
29、〈整数〉〈标识符〉-〉〈标识符〉〈字母〉
30、〈标识符〉〈数字〉
31、〈字母〉〈整数〉-〉
32、〈数字〉
33、〈整数〉〈数字〉〈字母〉-〉A
34、B
35、C〈数字〉
36、->1
37、2
38、3(1)改写文法G为G’,使L(G’)=L(G)。(2)给出相应的有穷自动机。解:(1)令D代表单词,I代表标识符,Z代表整数,有G’(D):D→I
39、ZI→A
40、B
41、C
42、IA
43、IB
44、IC
45、I1
46、I2
47、I3Z→1
48、2
49、3
50、Z1
51、Z2
52、Z3(2)左线性文法G’所对应的有穷自动机为:M=({S,D,I,Z},{1,2,3,A,B,C},f,S,{D})f:f(S,A)=I,f(S,B)=I,f(S,C)=If(S,1)=Zf(S,2)=Zf(