編譯原理第4章答案

第四章詞法分析

1.構(gòu)造下列正規(guī)式相應(yīng)的DFA：

⑴1(0|1)101

⑵1(1010*11(010)*1)*0

(S)a((a|b)*|ab*a)*b

(4)b((ab)*|bb)*ab

解：

(1)1(0|1)101對應(yīng)的NFA為

0G>

下表由子集法將NFA轉(zhuǎn)換為DFA：

IIo=￡-closure(MoveTo(l,0))li=￡-closure(MoveTo(l,1))

A[0]B[1]

B[1]B[1]C[1,2]

C[1,2]D[1.3]C[1,2]

D[1,3]B[1]E[1,4]

E[1,4]B[1]B[1]

下表由子集法將NFA轉(zhuǎn)換為DFA：

o=s-closure(MoveTo(1,0))1=E-closure(MoveTo(l,1))

A[0]B[1,6]

B[1,6]C[10]D[2,5,7]

C[10]

D[2,5,7]E[3,8]B[1,6]

E[3,8],F[1,4,6,9]

F[1,4,6,9]G(1.2,5,6,9,10]D[2,5,7]

G[1,2,5,6,9,10]H[1.3,6,9,10]l[1,2,5,6,7]

H[1,3,6,9,10]J[1,5.9.10]K[2,4,5,7]

l[1,2,5.67]L[3,8.10]1(1.2,5,67]

J[1.6,9,10]J[1,3,9,10]D[2,5,7]

K[2,4,5,7]M[2,3,5,8]B[1,6]

■

L[3,8,10]F[1,4,6,9]

M[2,3,5,8]N[3]?tF[1,4,6,9]

N[3]O[4]

0[4]P[2,5]

P[2,5]N(3):B[1,6]

0

(3)a((a|b)*|ab*afb(略)

(4)b((ab)*|bb)*ab(略)

2.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)=2,M(z,1)={y},

構(gòu)造相應(yīng)的DFAo

解：根據(jù)題總有NFA圖如下

0

下表由子集法將NFA轉(zhuǎn)換為DFA：

1--------------------------------------------------------------1----------------------------------------------------------------------------------

o=€-closure(MoveTo(l,0))1=e-closure(MoveTo(l,1))

A[x]B[z]A[x]

B[z]C[x,z]D[y]

C[x,z]C[x,z]E[x,y]

DM.E[x.y].

中MF[x,y,z]A[x]

F[x,y,z]F[x,y,z]EMy]

110

下面招該DFA最小化：

(1)首先將它的狀態(tài)集分成兩個子集：P={A,D,E},P={B,C,F)

(2)區(qū)分P:由于F(F,1)=F(CS1)=E,F(F,O)=F并且F(C,0)=3,所以F,C等價。由于F(B,O)=F(C,O)=C,F(B,1)=D,F(C,1)=E,

而D,E耒等價(見下步)，從而B與C,F可以區(qū)分。有P-{C.F}.P-{B}：

2122

(3)區(qū)分P1:由于A,E輸入。到終態(tài)，而D輸入。不到終態(tài)，所以D與A,E可以區(qū)分，有P"={A,E},Pi2={D}。

(4)由于口從0)=8下位,0)=兄而8,F不等價，所以A,E可以區(qū)分。

(5)綜上所述，DFA可以區(qū)分為P={{A},{B},{D},{E},{C.F}}。所以最小化的DFA如下：

解：下表由于集法將NFA轉(zhuǎn)換為DFA：

IIo=e-closure(MoveTo(l,0))h=e-closure(MoveTo(l,1))

A[S]B[Q,V]C[Q,U]

B[Q,V]DMZ1C[Q,U1

CfQ.Ul日V]FfQ.U.Zl

D[V,Z1G[Zl,G[Z].

EMG[Z]

F[Q,U,Z]D[V,Z]F[Q,U,Z]

G[Z]G[Z]G[Z]

1

4.把醫(yī)的(a)和(b)分別確定化和最小化:

匚

b

b

(b)

解:

⑻：

下表由子集法將NFA轉(zhuǎn)換為DFA：

Ila=E-closure(MoveTo(l,a))lb=E-closure(MoveTo(l,b))

A[0]B[0,1]cn

B[0,1]B[0,1]C[J

C[1]A[0]

可得圖(a1),由于F(A,b)=F(B,b)=C，并且F(A,a)=F(B,a)=B,所以A,B等價，可將DFA最小化，即:刪除B,將

原來引向B的引線引向與其等價的狀態(tài)A,有圖值2)。(DFA的最小化,也可看作將上表中的B全部替換為A,

然后刪除B所在的行。)

口

(a1)確定化的DFA(a2)最小化的DFA

(b)：該圖已經(jīng)是DFA.下面將該DFA最小化:

首先將它的狀態(tài)集分成兩個子集：Pi={0},P2=(123,4,5}

區(qū)分P：由于F(4,a)=0屬十終態(tài)集，血其他狀態(tài)輸入a后都是非終態(tài)集，所以區(qū)分P如下:

22

P2i={4},Pz2={1,2,3,5}°

(3)區(qū)分P22油于F(1,b)=F(5,b)=4屬于P2i,而F(2,b)與F(3,b)不等于4,即不屬于P2i,所以區(qū)分P22如下:

P221={1,5},P222={2,3}。

⑼區(qū)分P:由于F(1,b)=F(5,b)=4,即F(1,a)=1,F(5,a)=5,所以1,5等價。

221

(10)區(qū)分P222：由于F(2,a)=1屬于P%,而F(3,a)=3屬于P222,所以2,3可區(qū)分。Pzzz區(qū)分為P222i{2},Pzzzz{3}<>

(11)結(jié)論：該DFA的狀態(tài)集可分為:P={{0},{1,5},{2},{3},{4}},其中1,5等價。刪去狀態(tài)5,將原來引向5的引

線引向與其等價的狀態(tài)1,有圖(t1)0

(b1)最小化的DFA

5.構(gòu)造一個DFA,它接收Z={0,1}上所有滿足如下條件的字符串：每個1都有。直接跟在右邊。然后再構(gòu)造該

語曹的正則文法。

解：根據(jù)題意，DFA所對應(yīng)的正規(guī)式應(yīng)為：(0|(10))<.所以，接收該串的NFA如下:

下表由于集法將NFA轉(zhuǎn)換為DFA：

1------------------------------------------------1

o=€-closure(MoveTo(l,0))i=e-closure(MoveTo(l,1))

A[0]B[0,2]C[1]

B[0,2]B[0,2]C[1]

C[1]B[0,2]

顯然，A,B等價，所以將上述DFA最小化后有:

對應(yīng)的正規(guī)文法為:

G[A]：

A1C|OA|e

COA

6.設(shè)無符號數(shù)的正規(guī)式為0:

6=dd*|dd*.dd*|.dd*|dd*e(s|E)dd,|e(s|￡)dd*|.dd*e(s|E)dd*|dd*.dd*e(s|z)dd*

化簡6，畫出6的DFA,其中d={0,1,2,-9},s={+「

解：把原正規(guī)式的每2,3項，4,5項，6,7項分別合并后化筒有：

€=dd*|d*.dd*|d*e(s|z)dd*|d*.dd*e(s|

E)dd*=dd*|d*.dd*|(d*|d*.dd*)e(s|e:def

=(e|d*.|(d*|d*.dd*)e(s|￡))dd'

=(￡|d*.|d*(e|.dd')e(s|￡))dd

下面構(gòu)造化簡后的0對應(yīng)的NFA：

下表由子集法將NFA轉(zhuǎn)換為DFA：

1Id=c-closure(MoveT'O(l.dnle=c*closure(MoveTo(l.e))lsse*clo$urefMoveTofl.sHl.=c-closure(MoveTo(l,.))

A[0.1.4.6]B[1.7]C[5.6]D[2,6]

B[1.7]B[1.7]D[2,6]

crs61E[7]F(6]

DF2.61GF3.4.71

日71日71

F(A1F[7]

A[3,4,7]-------fi[3,4,7]-----------------------------------------------------

7一給文法G[S]：

SaA|bQ

AaA|bB|b

BbDlaQ

QaQ|bD|b

DbB|aA

EaB|bF

FbD|aE|b

構(gòu)造相應(yīng)的最小的DFAo

解：由于從S出發(fā)任何輸入串都不能到達狀態(tài)E和F,所以，狀態(tài)E,F為多余的狀態(tài)，不予考慮。這樣，可以

寫出文法G[S]對應(yīng)的NFA：

下表由子集法將NFA轉(zhuǎn)換為DFA：

1la=E-closure(MoveTo(l,a))lb=€-closure(MoveTo(l,b))

1[S]2[A],3[Q]

2[A]2[A]4[B,Z]

3[Q]3[Q]5[C,Z]

4B,Z]3[Q]6[C]

5[D,Z]2[A]7[B]

6[D]2[A]7[B]

7[B]3[Q]6[C]

由上表可知：

(1)因為4,5是DFA的終態(tài)，其他是非終態(tài)，可將狀態(tài)集分成兩個子集：

12

P-{1.2.3.6.7},P-(4.5}

(2)在Pl中因為2,3輸入b后是終態(tài)，而1,6,7輸入b后是非終態(tài)，所以Pl可區(qū)分為：

Pn={1,6,7},Pi2={2,3}

⑶在P11中由于1輸入b后為3,6輸入b后為7,而3,7分屬P”和Pi2,所以1與6不等價，同理，1與7不

等價。所以P11可區(qū)分為：

Pm={1},P112={6,7}

(4)查看P={6,7},由于輸入a后為2,3,所以6,7是否等價由2,3是否等價決定。

112

⑸查看口2={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分別改為對應(yīng)的等價狀態(tài)為2,4,6有下表:

--------------------------------1---------------------------------------------------------------------1-------------------------------------------------------------------1-------------------------------

ab

1[S]2[A]2[A]

2[A]2[A]4[B,Z]

4B,Z]2[A]6[C]

6[D]2[A]6[C]

這樣可得最小化的DFA如下:

8.給出下述文法所對應(yīng)的正規(guī)式：

S0A|1B

A1S|1

BOS|O

解：把后兩個產(chǎn)生式代入第一個產(chǎn)生式有：

S=01|01S

S=10|10S

有:S=01S|10S|01110=(01110)S|(01110)=(01110)*(01|10)

即:(01|10)*(01110)為所求的正規(guī)式。

9.將圖的DFA最小化，并用正規(guī)式描述它所識別的語言：

圖

解：

(1)因為6,7是DFA的終態(tài)，