资源描述：
《编译原理第2章习地训练题目课》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
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
6、？NFA化为DFA：Qab{X12}{123}{124}{123}{1235Y}{124}{124}{123}{1245Y}{1235Y}{1235Y}{124Y}{1245Y}{123Y}{1245Y}{124Y}{123Y}{1245Y}{123Y}{1235Y}{124Y}a所以，DFA为：X123456ababbabbabaab化简得：1XY2baababab精彩文档实用标准文案0εε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
8、}Y{AY}BABYX10100110化简后得；XA1001精彩文档实用标准文案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ÞACa精彩文档实用标准文案3.构造一个DFA，它接受∑={0，1}上所有满足如下条件的字符串，每个1都有0直接跟在后边。解：按题意相应的正规表达式是0*(0
9、10)*0*构造相应的DFA，首先构造NFA为000310XεεεεY102用
10、子集法确定化II0I1S01{X,0,1,3,Y}{0,1,3,Y}{2}{1,3,Y}{0,1,3,Y}{0,1,3,Y}{1,3,Y}{1,3,Y}{2}{2}/{2}12342244333DFA为01021101340精彩文档实用标准文案4.给出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)*11精
16、彩文档实用标准文案5.试证明正规式（a
17、b）*与正规式（a*
18、b*）*是等价的。a证明：(1)Y1X正规式(a
19、b)*的NFA为=>εεbab{X,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.设字
23、母表∑={a,b},给出∑上的正规式R=b*ab(b
24、ab)*。（1）试构造状态最小化的DFAM，使得L（M）=L（R）。（2）求右线性文法G，使L（G）=L（M）。解:(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}6精彩文档实用标准文案123456abbababbba再将其最小化得:XWYabbab（2）对应的右线性文法G=（{X,W,Y},{a,
25、b},P,X）P:X→aW
26、bXW→bY
27、by→aW
28、bY
29、b精彩文档实用标准文案3.8文法G[〈单词〉]为：〈单词〉-〉〈标识符〉
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)左线性
