编译原理第章答案

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的输入，所以不是确定的自动机。要将其他确定化,必须先用代入法得到它对应的