编译原理第章答案_第1页
编译原理第章答案_第2页
编译原理第章答案_第3页
编译原理第章答案_第4页
编译原理第章答案_第5页
已阅读5页,还剩7页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、词 法 分 析1.构造下列正规式相应的DFA(1) 1(0|1) * 101(2) 1(1010* | 1(010) * 1)*0(3) a(a|b) *|ab*a)* b(4) b(ab) * | bb) * ab解:(1)1(0|1) * 101 对应的 NFA为下NFA转1表由子集法将换为DFAII 0 = e -closure(MoveTo(I,0)11 =e -closure(MoveTo(I,1)A0B1B1B1C1,2C1,2D1,3C1,2D1,3B1E1,4E1,4B1B1* *(2)1(1010 | 1(010)-A10,100下 表由子 集法将 NFA转 换 为DFAII

2、 0 = £ -closure(MoveTo(I,0)11 =£ -closure(MoveTo(I,1)A0B1,6B1,6C10D2,5,7C10D2,5,7E3,8B1,6E3,8F1,4,6,9F1,4,6,9G1,2,5,6,9,10D2,5,7G1,2,5,6,9,10H1,3,6,9,10I1,2,5,6,7H1,3,6,9,10J1,6,9,10K2,4,5,7I1,2,5,6,7L3,8,10I1,2,5,6,7J1,6,9,10J1,6,9,10D2,5,7K2,4,5,7M2,3,5,8B1,6L3,8,10F1,4,6,9M2,3,5,8N3F1,4

3、,6,9N3O4O4P2,5P2,5N3B1,61I1 < 0 一 1KDHKE1 一 - I;'、000100p0010(3)a(a|b),|ab*a) *b(略)(4)b(ab) * | bb) *ab (略)2. 已知 NFA= (x,y,z,0,1,M,x,z)其中:M(x,0)=z,M(y,0)=x,y,M(z,0)=x,z,M(x,1)=x, M(y,1)=0 ,M(z,1)=y,构造相应的DFA解:根据题意有NFA图如下010下表向了集注将NFA转换手;DFA0ssTkI 0 = e -closure(MoveTo(I,0)11 =e -closure(MoveTo

4、(I,1)Ax0BzAxBzCx,zDyCx,zCx,zEx,yDyEx,yEx,yFx,y,zAxFx,y,zFx,y,zEx,yF面将该DFA最小化:(1)首先将它的状态集分成两个子集:Pi=A,D,E,P 2=B,C,F(2)区分 P2:由于 F(F,1)=F(C,1)=E,F(F,0)=F 并且 F(C,0)=C,所以 F, C 等价。由于 F(B,0)=F(C,0)=C, F(B,1)=D,F(C,1)=E, 而 D, E 不等价(见下步),从而 B 与 C, F 可以区分。有 Bi=C,F,P 22=B。(3) 区分P1:由于A, E输入0到终态,而D输入0不到终态,所以D与A,

5、E可以区分,有Pn=A,E,P 12=D(4) 由于F(A,0)=B,F(E,0)=F, 而B, F不等价,所以 A, E可以区分。(5) 综上所述,DFA可以区分为P=A , B , D, E , C , F。所以最小化的 DFA如下:13.将图4.16确定化:0-iA-_0,4.16y-卜去由于净陶Nfa转1 为 dfaku也0, 1#一11、I 0 = £ -ciqsure(MoveTo(I,0) /11 =T-JU_-<e -closure(MoveTo(I,1)ASa!BQ,V11CQ,UBQ,VDV,ZCQ,UCQ,UEVFQ,U,ZDV,ZGZGZEVGZFQ,U

6、,ZDV,ZFQ,U,Z解:GZGZGZ4,把图和(b)分4.17 的(a)1别确定化和解:(a):(b)F表由子集法将NFA转换为DFAIla = £ -closure(MoveTo(I,a)I b =e -closure(MoveTo(I,b)A0B0,1C1B0,1B0,1C1C1A0并且F(A,a)=F(B,a)=B, 所以A,B等价,可将 DFA最小化,即:删除可得图(a1),由于 F(A,b)=F(B,b)=C, B,将原来引向B的引线引向与其等价的状态 A,然后删除B所在的行。)A,有图(a2) o (DFA的最小化,也可看作将上表中的B全部替换为定化的小化的该图已DF

7、A最DFADFA经是DFA下面 小化:(6)首先将它的状态集分成两个子集:P1=0,P区分P2:由于 F(4,a)=0 属于终态集,2=1,2,3,4,5而其他状态输入a后都是非终态集,所以区分F2如下:最小化:P2i=4,P 22=1,2,3,5(8)区分 P22:由于 F(1,b)=F(5,b)=4属于P21,而F(2,b)与F(3,b)不等于4,即不属于F21,所以区分P22如下:P221=1,5,P222=2,3区分 P221:由于 F(1,b)=F(5,b)=4,(10)区分P222:由于F(2,a)=1 属于即 F(1,a)=1,F(5,a)=5, 所以 1,5 等价。P221,而

8、 F(3,a)=3 属于 自22,所以 2, 3 可区分。P222 区分为 P22212 , P2222G。(11)结论:该 DFA 的状态集可分为:P= 0,1,5,2,3,4 ,其中1,5等价。删去状态 5,将原来引向5的引线引向与其等价的状态1,有图(b1)(b1)最小化的DFA5.构造一个 DFA,它接收E 的字符串:每个1都有0直接 言的正则文法。解:根据题意,DFA为:(0|(10)。所以,=0, 1上所有满足如下条件 跟在右边。然后再构造该语所对应的正规式应接收该串的 NFA如下:F表由子集法将NFA转换为DFAII 0 = e -closure(MoveTo(I,0)11 =&

9、#163; -closure(MoveTo(I,1)A0B0,2C1B0,2B0,2C1C1B0,2二°显然,A, B等价,所以将上述0FA最小化后有:0对应的正规文法为:GA:A 1C|0A| &C 0A6.设无符号数的正规式为e :0 =dd*|dd *.dd *|.dd *|dd *e(s| e )dd ,|e(s| e )dd *|.dd *e(s| e )dd*|dd *.dd *e(s| e )dd* 化简 0 ,画出。的 DFA 其中 d=0,1,2,9,s=+,-解:把原正规式的每2, 3项,4, 5项,6, 7项分别合并后化简有:e =dd |d .dd |

10、d e(s| e )dd |d .dd e(s| e )dd=dd*|d *.dd *|(d *|d *.dd *)e(s|e )dd *=(e |d *.|(d *|d *.dd *)e(s| e )dd *=(e |d .|d ( e |.dd )e(s| Odd下面构造化简后的0对应的NFA£e5d表由子集法将转换为DFAGS:S aA|bQA aA|bB|bIId=£ -closure(MoveTo(I,d)I e= £-closure(MoveTo(I,e)I s= £ -closure(MoveTo(I,s)I . = s -closure(

11、MoveTo(I,.)A0,1,4,6B1,7C5,6D2,6B1,7B1,7D2,6C5,6E7F6D2,6G3,4,7E7E7F6E7G3,4,7G3,4,7C5,6B bD|aQ Q aQ|bD|b D bB|aA E aB|bF F bD|aE|b 构造相应的最小的DFA解:由于从S出发任何输入串都不能到达状态E和F,所以,状态E, F为多余的状态,不予考虑。这样,可以写出文法 GS对应的NFA下表a转换为0 ©aDFAQ aa bab _一 b由子集法将 NFAII a = e -closure(MoveTo(I,a)I b =£ -closure(MoveTo(

12、I,b)1S2A3Q2A2A4B,Z3Q3Q5D,Z4B,Z3Q6D5D,Z2A7B6D2A7B7B3Q6D由上表可知:(1)因为4, 5是DFAW终态,其他是非终态,可将状态集分成两个子集:Pi=1, 2, 3, 6, 7, P2=4, 5 在Pi中因为2,3输入b后是终态,而1, 6, 7输入b后是非终态,所以Pi可区分为:Pii=1 , 6, 7, Pi2=2, 3在Pii中由于1输入b后为3, 6输入b后为7,而3, 7分属Pii和P%所以 1与6不等价,同理,i与7不等价。所以Pii可区分为:Piii=i , Pii2=6, 7(4)查看Pii2=6, 7,由于输入a后为2, 3,所

13、以6, 7是否等价由2, 3是否等 价决定。(5)查看Pi2=2, 3,由于输入b后为4, 5,所以2, 3是否等价由4, 5是否等 价决定。(6)查看P2=4, 5,显然4, 5是否等价由2, 3与6, 7是否同时等价决定。 由于有(4)即6, 7是否等价由2, 3是否等价决定,所以,4, 5是否等价由2, 3是否等价决定。由于有(5)即2, 3是否等价由4, 5是否等价决定,所以有 4, 5等价,2, 3等价,进而6, 7也等价。(7)删除上表中的第3, 5, 7行,并将剩余行中的3, 5, 7分别改为对应的等价 状态为2, 4, 6有下表:II aI biS2A2A2A2A4B,Z4B,

14、Z2A6D6D2A6D这样可得最小化的DFA如下:6L:b8 .给出下述文法所对应的正规式:S 0A|1BA 1S|1B 0S|0解:把后两个产生式代入第一个产生式有:S=01|01SS=10|10S有:S=01S|10S|01|10=(01|10)S|(01|10)=(01|10)*(01|10)即:(01|10) *(01|10)为所求的正规式。9 .将图4.18的DFA最小化,并用正规式描述它所识别的语言:解:d因为6, 7同DFA的终态,泼他愚兼变,P1=1, 2, 3, 4±5, P2=6,察9由于 F(6,b)=F(7,b)a b§、b可将状态集分成两个子集:b

15、6, 7又没有其彳 ,所以 6, 7"而6, 7等价,所以3,4等价。(3)由于 F(3,c)=F(4,c)=3,F(3,d)=F(4,d)=5,F(3,b)=6,F(4,b)=7,(1)由于 F(1,b)=F(2,b)=2,F(1,a)=3,F(2,a)=4, 而 3, 4 等价,所以 1,2 等价。(2)由于状态5没有输入字符b,所以与1, 2, 3, 4都不等价。综上所述,上图DFA的状态可最细分解为:P=1 , 2, 3, 4, 5 , 6, 7b a(c|da) bb该DFA用正规式表?为)* *10 .构造下述文法 GS的自动机:S A0A A0|S1|0该自动机是确定的吗?若不确定,则对它确定化。该自动机相应的语言是什么? 解:由于该文法的产生式 S A0, A A0|S1中没有字符集 Vt的输入,所以不是确定的自动机。要将其他确定化,必须先用代入法得到它对应的

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论