編譯原理答案

1、第四章 詞法分析1構(gòu)造下列正規(guī)式相應(yīng)的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對應(yīng)的NFA為01231104110下表由子集法將NFA轉(zhuǎn)換為DFA：II0 = -closure(MoveTo(I,0)I1 = -closure(MoveTo(I,1)A0B1B1B1C1,2C1,2D1,3C1,2D1,3B1E1,4E1,4B1B1ABCD110E11000,11(2)1(1010* | 1(010)* 1)* 0對應(yīng)的NFA為02

2、451101010361079810011下表由子集法將NFA轉(zhuǎn)換為DFA：II0 = -closure(MoveTo(I,0)I1 = -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,

3、8,10F1,4,6,9M2,3,5,8N3F1,4,6,9N3O4O4P2,5P2,5N3B1,6AB1C0D1E01F101H0G1I0K1J10L01M0011NOP011001(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)=,M(z,1)=y,構(gòu)造相應(yīng)的DFA。xy0z010010解：根據(jù)題意有NFA圖如下下表由子集法將NFA轉(zhuǎn)換為DFA：II0 = -closure(MoveTo(I,0)I1

4、 = -closure(MoveTo(I,1)AxBzAxBzCx,zDyCx,zCx,zEx,yDyEx,yEx,yFx,y,zAxFx,y,zFx,y,zEx,y01100BCEF00DA1101下面將該DFA最小化：(1) 首先將它的狀態(tài)集分成兩個子集：P1=A,D,E,P2=B,C,F(2) 區(qū)分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(xiàn)可以區(qū)分。有P21=C,F,P22=B。(3) 區(qū)分P1:由于A，E輸入0到終態(tài)，而

5、D輸入0不到終態(tài)，所以D與A，E可以區(qū)分，有P11=A,E,P12=D。(4) 由于F(A,0)=B,F(E,0)=F,而B，F(xiàn)不等價，所以A，E可以區(qū)分。(5) 綜上所述，DFA可以區(qū)分為P=A，B，D，E，C，F(xiàn)。所以最小化的DFA如下：11010F0BE10DA03.將圖4.16確定化：S0，1Z1V11U0Q0，1001圖4.16解：下表由子集法將NFA轉(zhuǎn)換為DFA：II0 = -closure(MoveTo(I,0)I1 = -closure(MoveTo(I,1)ASBQ,VCQ,UBQ,VDV,ZCQ,UCQ,UEVFQ,U,ZDV,ZGZGZEVGZFQ,U,ZDV,ZFQ,U

6、,ZGZGZGZAGDB0，10C110E010F010，14.把圖4.17的(a)和(b)分別確定化和最小化：12435bbbbaaa0abaab01aa,ba(a) (b)解：(a):下表由子集法將NFA轉(zhuǎn)換為DFA：IIa = -closure(MoveTo(I,a)Ib = -closure(MoveTo(I,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全部替

7、換為A，然后刪除B所在的行。）AabCaBbaAbCaa（a1）確定化的DFA （a2）最小化的DFA（b）:該圖已經(jīng)是DFA。下面將該DFA最小化：(6) 首先將它的狀態(tài)集分成兩個子集：P1=0,P2=1,2,3,4,5(7) 區(qū)分P2：由于F(4,a)=0屬于終態(tài)集，而其他狀態(tài)輸入a后都是非終態(tài)集，所以區(qū)分P2如下：P21=4,P22=1,2,3,5。(8) 區(qū)分P22:由于F(1,b)=F(5,b)=4屬于P21,而F(2,b)與F(3,b)不等于4,即不屬于P21，所以區(qū)分P22如下：P221=1,5,P222=2,3。(9) 區(qū)分P221:由于F(1,b)=F(5,b)=4,即F(1

8、,a)=1,F(5,a)=5,所以1,5等價。(10) 區(qū)分P222:由于F(2,a)=1屬于P221，而F(3,a)=3屬于P222,所以2，3可區(qū)分。P222區(qū)分為P22212，P22223。1243bbaa0abaabb(11) 結(jié)論：該DFA的狀態(tài)集可分為：P= 0,1,5,2,3,4 ,其中1,5等價。刪去狀態(tài)5，將原來引向5的引線引向與其等價的狀態(tài)1，有圖(b1)。(b1)最小化的DFA5構(gòu)造一個DFA，它接收=0，1上所有滿足如下條件的字符串：每個1都有0直接跟在右邊。然后再構(gòu)造該語言的正則文法。解：根據(jù)題意，DFA所對應(yīng)的正規(guī)式應(yīng)為：(0|(10)*。所以，接收該串的NFA如下

9、：012100下表由子集法將NFA轉(zhuǎn)換為DFA：II0 = -closure(MoveTo(I,0)I1 = -closure(MoveTo(I,1)A0B0,2C1B0,2B0,2C1C1B0,211000BCA顯然，A，B等價，所以將上述DFA最小化后有：0C1A0對應(yīng)的正規(guī)文法為：GA：Aà1C|0A|Cà0A6設(shè)無符號數(shù)的正規(guī)式為：=dd*|dd*.dd*|.dd*|dd*e(s|)dd*|e(s|)dd*|.dd*e(s|)dd*|dd*.dd*e(s|)dd* 化簡,畫出的DFA，其中d=0,1,2,9,s=+,-解：把原正規(guī)式的每2，3項(xiàng)，4，5項(xiàng)，6，7項(xiàng)分

10、別合并后化簡有：=dd*|d*.dd*|d*e(s|)dd*|d*.dd*e(s|)dd*=dd*|d*.dd*|(d*|d*.dd*)e(s|)dd*=(|d*.|(d*|d*.dd*)e(s|)dd*=(|d*.|d*(|.dd*)e(s|)dd*下面構(gòu)造化簡后的對應(yīng)的NFA：57ed421.3dd6sdd.0 下表由子集法將NFA轉(zhuǎn)換為DFA：IId =-closure(MoveTo(I,d)Ie=-closure(MoveTo(I,e)Is=-closure(MoveTo(I,s)I.=-closure(MoveTo(I,.)A0,1,4,6B1,7C5,6D2,6B1,7B1,7D2

11、,6C5,6E7F6D2,6G3,4,7E7E7F6E7G3,4,7G3,4,7C5,6ED.ddCGdBd.AeesFddd7給文法GS：SàaA|bQAàaA|bB|bBàbD|aQQàaQ|bD|bDàbB|aAEàaB|bFFàbD|aE|b構(gòu)造相應(yīng)的最小的DFA。解：由于從S出發(fā)任何輸入串都不能到達(dá)狀態(tài)E和F，所以，狀態(tài)E，F(xiàn)為多余的狀態(tài)，不予考慮。這樣，可以寫出文法GS對應(yīng)的NFA：aZSADQBbbbababbbaa下表由子集法將NFA轉(zhuǎn)換為DFA：IIa = -closure(MoveTo(I,a)Ib =

12、-closure(MoveTo(I,b)1S2A3Q2A2A4B,Z3Q3Q5D,Z4B,Z3Q6D5D,Z2A7B6D2A7B7B3Q6D由上表可知：(1)因?yàn)?，5是DFA的終態(tài)，其他是非終態(tài)，可將狀態(tài)集分成兩個子集：P1=1，2，3，6，7，P2=4，5 (2)在P1中因?yàn)?,3輸入b后是終態(tài)，而1，6，7輸入b后是非終態(tài)，所以P1可區(qū)分為：P11=1，6，7，P12=2，3 (3)在P11中由于1輸入b后為3，6輸入b后為7，而3，7分屬P11和P12，所以1與6不等價，同理，1與7不等價。所以P11可區(qū)分為：P111=1，P112=6，7(4)查看P112=6，7，由于輸入a后為2，

13、3，所以6，7是否等價由2，3是否等價決定。(5)查看P12=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等價,進(jìn)而6，7也等價。(7)刪除上表中的第3，5，7行，并將剩余行中的3，5，7分別改為對應(yīng)的等價狀態(tài)為2，4，6有下表：IIa Ib 1S2A2A2A2A4B,Z4B,Z2A6D6D2A6D這樣可得最小化的DFA如下：

14、a41b2aaabb6b8給出下述文法所對應(yīng)的正規(guī)式：Sà0A|1BAà1S|1Bà0S|0解：把后兩個產(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)*(01|10)為所求的正規(guī)式。9將圖4.18的DFA最小化，并用正規(guī)式描述它所識別的語言：a72bcbdb134c6aabbd5b圖 4.18解：(1) 因?yàn)?，7是DFA的終態(tài)，其他是非終態(tài)，可將狀態(tài)集分成兩個子集：P1=1，2，3，4，5，P2=6，7。(2) 由于F(6,b)=F(

15、7,b)=6,而6，7又沒有其他輸入，所以6，7等價。(3) 由于F(3,c)=F(4,c)=3,F(3,d)=F(4,d)=5,F(3,b)=6,F(4,b)=7,而6，7等價，所以3,4等價。(1) 由于F(1,b)=F(2,b)=2,F(1,a)=3,F(2,a)=4,而3，4等價，所以1,2等價。(2) 由于狀態(tài)5沒有輸入字符b,所以與1，2，3，4都不等價。(3) 綜上所述，上圖DFA的狀態(tài)可最細(xì)分解為：P=1，2，3，4，5，6，7。abb13c6bd5a該DFA用正規(guī)式表示為：b*a(c|da)*bb*10構(gòu)造下述文法GS的自動機(jī)：SàA0AàA0|S1|0該自動機(jī)是確定的嗎？若不確定，則對它確定化。該自動機(jī)相應(yīng)的語言是什么？解：由于該文法的產(chǎn)生式SàA0，AàA0|S1中沒有字符集VT的輸入，所以不是確定的自動機(jī)。要將其他確定化，必須先用代入法得到它對應(yīng)的正規(guī)式。把SàA0代入產(chǎn)生式