編譯原理第4章答案

1、第四章詞法分析1構(gòu)造以下正規(guī)式相應的DFA(1) 1(0 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為(2)1(101011££F表由子集法將NFA轉(zhuǎn)換為DFAI10 = e -closure(MoveTo(l,0)I 1 =e -closure(MoveTo(l,1)A0B1B1B1C1,2C1,2D1,3C1,2D1,3B1E1,4E1,4B1B111F000J00KMN|ab a) b (| bb) * ab (3)

2、 a(a|b)(4) b(ab)2. NFAx,y,z,0,1,M,x,z0 ,M(z,1)=y,構(gòu)造相應的 DFA解：根據(jù)題意有NFA圖如下其中：M(x,0)=z,M(y,0)=x,y,M(z,0)=x,z,M(x,1)=x,M(y,1)=:x :'0F表由子集法將NFA轉(zhuǎn)換為DFAI10 = £ -closure(MoveTo(l,0)I 1 =£ -closure(MoveTo(l,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,10

3、H1,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,6,9N3O4O4P2,5P2,5N3B1,6F表由子集法將NFA轉(zhuǎn)換為DFAI10 = e -closure(MoveTo(l,0)I 1 =e -closure(MoveTo(l,1)AxBzAxBzCx,zDyCx,zCx,zEx,yDyEx,yEx,yFx,y,zAxFx,y,zFx,y,z

4、Ex,y1101F面將該DFA最小化:(1)首先將它的狀態(tài)集分成兩個子集：Pi=A,D,E,P 2=B,C,F(2)區(qū)分 F2:由于 F(F,1)=F(C,1)=E,F(F,0)=F 并且 F(C,O)=C,所以 F, C 等價。由于F(B,O)=F(C,O)=C,F(B,1)=D,F(C,1)=E, 而 D, E 不等價見下步，從而 B 與 C, F 可以區(qū)分。有 P21=C,F,P 22=B。 區(qū)分P1：由于A，E輸入0到終態(tài)，而D輸入0不到終態(tài)，所以D與A，E可以區(qū)分，有Pn=A,E,P 12=D(4)由于F(A,0)=B,F(E,0)=F, 而B, F不等價，所以 A，E可以區(qū)分。綜上

5、所述，DFA可以區(qū)分為P=A，B，D，E，C，F(xiàn)。所以最小化的 DFA如下:13將圖4.16確定化:解:I10 = e -closure(MoveTo(I,0)I 1 =£ -closure(MoveTo(l,1)ASBQ,VCQ,UBQ,VDV,ZCQ,UCQ,UEVFQ,U,ZDV,ZGZGZEVGZFQ,U,ZDV,ZFQ,U,ZGZGZGZ0CE011FG00BD0, 111A0B4.把圖4.17的 和(b)分別確定化和最小化:解：(a)：F表由子集法將NFA轉(zhuǎn)換為DFAIIa = £ -closure(MoveTo(I,a)I b =£ -closure

6、(MoveTo(l,b)A0B0,1C1B0,1B0,1C1C1A0可得圖a1，由于F(A,b)=F(B,b)=C,并且F(A,a)=F(B,a)=B, 所以A,B等價，可將 DFA最小化，即：刪除B,將原來引向B的引線引向與其等價的狀態(tài)A,有圖(a2)。 DFA的最小化，也可看作將上表中的B全部替換為A，然后刪除B所在的行。aa1確定化的 DFAb：該圖已經(jīng)是 DFA下面將該 DFA最小化:a2最小化的 DFA首先將它的狀態(tài)集分成兩個子集：Pi=O,P 2=1,2,3,4,5區(qū)分P2 :由于F(4,a)=0屬于終態(tài)集，而其他狀態(tài)輸入a后都是非終態(tài)集，所以區(qū)分R如下：P2i=4,P 22=1,

7、2,3,5。(8) 區(qū)分P22：由于F(1,b)=F(5,b)=4 屬于P21,而F(2,b)與F(3,b)不等于4,即不屬于F2i，所以區(qū)分P22如下:P221=1,5,P222=2,3。(9) 區(qū)分 P221：由于 F(1,b)=F(5,b)=4, 即 F(1,a)=1,F(5,a)=5, 所以 1,5 等價。(10) 區(qū)分 P222：由于 F(2,a)=1 屬于 P221，而 F(3,a)=3 屬于 %,所以 2, 3 可區(qū)分。P222區(qū)分為 P22212，P2222Q(11) 結(jié)論：該DFA的狀態(tài)集可分為：P= 0,1,5,2,3,4 ,其中1,5等價。刪去狀態(tài)5，將原來引向5的引線引

8、向與其等價的狀態(tài)1,有圖(b1)。15 構(gòu)造一個 DFA它接收藝=0，1上所有滿足如下條件的字符串：每個 該語言的正那么文法。解：根據(jù)題意，DFA所對應的正規(guī)式應為：(0|(10) *。所以，接收該串的都有0直接跟在右邊。然后再構(gòu)造NFA如下:£F表由子集法將NFA轉(zhuǎn)換為DFAII 0= £ -closure(MoveTo(l,0)11= £ -closure(MoveTo(I,1)A0B0,2C1B0,2B0,2:C1C1B0,2對應的正規(guī)文法為：GA:A 1C|0A| £C 0A6 設無符號數(shù)的正規(guī)式為e：0 =dd*|dd*.dd *|.dd *|

9、dd *e(s| e )dd *|e(s| e )dd *|.dd *e(s| e )dd *|dd *.dd *e(s| e )dd 化簡 e ,畫岀 0 的 DFA 其中 d=0,1,2,9,s=+,-解：把原正規(guī)式的每2, 3項，4 , 5項，6, 7項分別合并后化簡有：0 =dd*|d *.dd *|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|e )dd

10、 *下面構(gòu)造化簡后的0對應的NFAF表由子集法將NFA轉(zhuǎn)換為DFAII d=e -closure(MoveTo(l,d)I e=e -closure(MoveTo(I,e)I s=e -closure(MoveTo(I,s)I . = e -closure(MoveTo(I,.)A0,1,4,6 B1,7C5,6D2,6B1,7B1,7D2,6C5,6E7F6D2,6G3,4,7E7E7F6E7G3,4,7G3,4,7C5,67 給文法GS:S aA|bQA aA|bB|bB bD|aQQ aQ|bD|bD bB|aAE aB|bFF bD|aE|b構(gòu)造相應的最小的 DFA解：由于從S岀發(fā)任何

11、輸入串都不能到達狀態(tài)E和F,所以，狀態(tài)E, F為多余的狀態(tài)，不予考慮。這樣，可以寫岀文法 GS對應的NFAF表由子集法將NFA轉(zhuǎn)換為DFAIla = £ -closure(MoveTo(l,a)I b =£ -closure(MoveTo(l,b)iS2A3Q2A2A4B,Z3Q3Q5D,Z4B,Z3Q6D5D,Z2A7B6D2A7B7B3Q6D由上表可知：(1)因為4, 5是DFA的終態(tài)，其他是非終態(tài)，可將狀態(tài)集分成兩個子集：Pi=1，2, 3，6，7，P2=4，5 在Pi中因為2,3輸入b后是終態(tài)，而1，6，7輸入b后是非終態(tài)，所以 Pi可區(qū)分為：Pii=1，6，7，P

12、i2=2，3在Pii中由于I輸入b后為3, 6輸入b后為7,而3，7分屬Pii和Pi2,所以I與6不等價，同理，I與 7不等價。所以 Pii可區(qū)分為：Piii=i , Pii2=6 , 7查看Pii2=6 , 7，由于輸入a后為2, 3,所以6, 7是否等價由2, 3是否等價決定。查看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是否

13、等價決定，所以有 4, 5等價，2, 3等價,進而6, 7也等價。(7) 刪除上表中的第3, 5, 7行，并將剩余行中的 3, 5, 7分別改為對應的等價狀態(tài)為2, 4, 6有下表：II albiS2A2A2A2A4B,Z4B,Z2A6D：6D2A6D8 給岀下述文法所對應的正規(guī)式:SA0A|1B1S|10S|0B解：把后兩個產(chǎn)生式代入第一個產(chǎn)生式有：S=01|01SS=10|10S有:S=01S|10S|01|10=(01|10)S|(01|10)=(01|10) 即:(01|10)*(01|10)為所求的正規(guī)式。9 將圖(01|10)4.18的DFA最小化，并用正規(guī)式描述它所識別的語言:b

14、bb4圖 4.18a 3解：(1)(1)因為7。由于由于由于6, 7是DFA的終態(tài)，其他是非終態(tài)，可將狀態(tài)集分成兩個子集:P1=1，2，3, 4, 5，P2=6，F(xiàn)(6,b)=F(7,b)=6, 而6，7又沒有其他輸入，所以6，7等價。F(3,c)=F(4,c)=3,F(3,d)=F(4,d)=5,F(3,b)=6,F(4,b)=7,而 6，F(xiàn)(1,b)=F(2,b)=2,F(1,a)=3,F(2,a)=4,而 3，4 等價，所以 1,2 等價。7等價，所以3,4等價。b由于狀態(tài)5沒有輸入字符b,所以與1，2，3，4都不等價。綜上所述，上圖DFA的狀態(tài)可最細分解為：P=1，2，3，4，5，6，7。這樣可得最小化的 DFA如下:b a(c|da) bb000XY10 構(gòu)造下述文法 GS的自動機:S A0A A0|S1|0解:該自動機是確定的嗎？假設不確定，那么對它確定化。該自動機相應的語言是什么？由于該文法的產(chǎn)生式 S A0, A A0|S1中沒有字符集 Vt的輸入，所以不是確定的自動機。要將其他確定化，必須先用代入法得到它對應的正規(guī)式。把