编译原理第4章答案

第四章词法分析

1.构造下列正规式相应的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对应的NFA为

0G>

下表由子集法将NFA转换为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转换为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},

构造相应的DFAo

解：根据题总有NFA图如下

0

下表由子集法将NFA转换为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)首先将它的状态集分成两个子集：P={A,D,E},P={B,C,F)

(2)区分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可以区分。有P-{C.F}.P-{B}：

2122

(3)区分P1:由于A,E输入。到终态，而D输入。不到终态，所以D与A,E可以区分，有P"={A,E},Pi2={D}。

(4)由于口从0)=8下位,0)=兄而8,F不等价，所以A,E可以区分。

(5)综上所述，DFA可以区分为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,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.把医的(a)和(b)分别确定化和最小化:

匚

b

b

(b)

解:

⑻：

下表由子集法将NFA转换为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的引线引向与其等价的状态A,有图值2)。(DFA的最小化,也可看作将上表中的B全部替换为A,

然后删除B所在的行。)

口

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

(b)：该图已经是DFA.下面将该DFA最小化:

首先将它的状态集分成两个子集：Pi={0},P2=(123,4,5}

区分P：由于F(4,a)=0属十终态集，血其他状态输入a后都是非终态集，所以区分P如下:

22

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

(3)区分P22油于F(1,b)=F(5,b)=4属于P2i,而F(2,b)与F(3,b)不等于4,即不属于P2i,所以区分P22如下:

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

⑼区分P:由于F(1,b)=F(5,b)=4,即F(1,a)=1,F(5,a)=5,所以1,5等价。

221

(10)区分P222：由于F(2,a)=1属于P%,而F(3,a)=3属于P222,所以2,3可区分。Pzzz区分为P222i{2},Pzzzz{3}<>

(11)结论：该DFA的状态集可分为:P={{0},{1,5},{2},{3},{4}},其中1,5等价。删去状态5,将原来引向5的引

线引向与其等价的状态1,有图(t1)0

(b1)最小化的DFA

5.构造一个DFA,它接收Z={0,1}上所有满足如下条件的字符串：每个1都有。直接跟在右边。然后再构造该

语曹的正则文法。

解：根据题意，DFA所对应的正规式应为：(0|(10))<.所以，接收该串的NFA如下:

下表由于集法将NFA转换为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最小化后有:

对应的正规文法为:

G[A]：

A1C|OA|e

COA

6.设无符号数的正规式为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={+「

解：把原正规式的每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

下面构造化简后的0对应的NFA：

下表由子集法将NFA转换为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

构造相应的最小的DFAo

解：由于从S出发任何输入串都不能到达状态E和F,所以，状态E,F为多余的状态，不予考虑。这样，可以

写出文法G[S]对应的NFA：

下表由子集法将NFA转换为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的终态，其他是非终态，可将状态集分成两个子集：

12

P-{1.2.3.6.7},P-(4.5}

(2)在Pl中因为2,3输入b后是终态，而1,6,7输入b后是非终态，所以Pl可区分为：

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

⑶在P11中由于1输入b后为3,6输入b后为7,而3,7分属P”和Pi2,所以1与6不等价，同理，1与7不

等价。所以P11可区分为：

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分别改为对应的等价状态为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.给出下述文法所对应的正规式：

S0A|1B

A1S|1

BOS|O

解：把后两个产生式代入第一个产生式有：

S=01|01S

S=10|10S

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

即:(01|10)*(01110)为所求的正规式。

9.将图的DFA最小化，并用正规式描述它所识别的语言：

图

解：

(1)因为6,7是DFA的终态，