編譯原理第4章答案2

第四章詞法分析

1.構造下列正規(guī)式相應的DFA：

(1)1(0|1)J01

(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為

0

1

下表由子集法將NFA轉換為DFA：

IIo=e-closure(MoveTo(l,0))h=€-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轉換為DFA：

o=e-closure(MoveTo(l,0))i=￡-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,67]

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

l[1,2,5,6,7]L[3,8,10]l[1,2,5,6,7]

J[1,6,9,10]J[1,6,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].,F[1,4,6,9]

N[3]O[4]

O[4]P[2,5]

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

0

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

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

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

構造相應的DFAO

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

0,7

0

下表由子集法將NFA轉換為DFA：

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

0=e-closure(MoveTo(l,0))1=￡-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]

D[y].E[x,y].

E[x,y]F[x,y,z]A[x]

F[x,y,z]F[x,y,z].E[x,y]

下面將該DFA最小化：

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

(2)區(qū)分P油于F(F,1)=F(C,1)=E,F(F,O)=FkiLF(CQ)=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輸入0不到終態(tài)，所以D與A,E可以區(qū)分，有Pn={A,E},PI2={D}。

(4)由于口兒0)=8下任。)=匕而8,F不等價，所以A.E可以區(qū)分。

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

解：下表由子集法將NFA轉換為DFA：

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

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

B[Q,V1DfV.ZlC[Q,U]

C[Q,U1E(V]F[Q,U.Zl

D[V,Z1GfZl:.G[Z]

E[V]G[Z]

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

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

4,把圖的(a)和(b)分別確定化和最小化;

b

a口

a

b

_b

a

a

b

(a)(b)

解：

下表由子集法將NFA轉換為DFA：

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

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

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

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,有圖(a2)。(DFA的最小化，也可看作將上表中的B全部替換為A,

然后刪除B所在的行。)

口

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

<b):該圖已經是DFA。下面將該DFA最小化:

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

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

2

P2i?{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}o

(9)區(qū)分P；由'于F(1$)=F(5,b)=4,即F(1,a)=1,F(5,a)=5,所以1,5等價。

221

(10)區(qū)分Pzzz:由于F(2,a)=1屬于P221,而F(3,a)=3屬于P222,所以2,3可區(qū)分。P222區(qū)分為Pz22i{2},P2222{3}<)

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

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

(b1)最小化的DFA

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

語言的正則文法。

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

下表由子集法將NFA轉換為DFA：

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

0=c-closure(MoveTo(l,0))1=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最小化后有:

對應的正規(guī)文法為：

G[A]：

A1C|0A|￡

COA

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

e=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，畫出6的DFA,其中d={0,1,2,…9),s={+.-

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

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

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

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

=(￡|d,|d(￡|.dd)e(s|?))dd

下面構造化簡后的。對應的NFA：

卜表由子集法將NFA轉換為DFA：

1Id=€-closure(MoveTo(Ld))le=￡*dosure(MoveTotl.eHls=￡-closure(MoveTo(LsBl.=E-closure(MoveTo(l,.))

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

B[1.7]D[2,6]

F[7]F[fi]

Df2,6lG⑶4.71

日71E(71

F同F(xiàn)[7]

013,4,71——G[3,4,7]------------------------CM----------------------------

7.給文法G[S]：

SaA|bQ

AaA|bB|b

BbD|aQ

QaQ|bD|b

DbB|aA

EaB|bF

FbD|aE|b

構造相應的最小的DFA.

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

寫出文法G[S]對應的NFA：

'a

下表由子集法將NFA轉換為DFA：

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

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

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

3[Q]3[Q]5[D,Z]

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

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

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

7[B]3[Q]6[D]

由上表可知：

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

12

P=<1.2.3.6.7}.P={4.5}

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

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

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

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

Pm={1kPii2={6，7}

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

112

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

--------------------------------1-----------------------------------1r

a.b

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

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

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

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

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

b

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

S0A|1B

A1S|1

BOS|O

解：把后兩個產生式代入第一個產生式有：

S=01|01S

S=10|10S

有:S=01S|10S|01110=(01|10)S|(01|10)={01|10)■(01|10)

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

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

解：

(1)因為6,7是DFA的終態(tài)，其他是非終態(tài)，可將狀態(tài)集分成兩個子集：P1={1,2,3,4,5},P2={6,

7}。

(2)由于F(6,b)=F(7,b)=6,而6,7又沒有其他輸入，所以6,7等價。

(3)由于F(3,c)=F(4,c