编译原理第4章答案2

第四章词法分析

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

解：根据题意有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)首先将它的状态集分成两个子集：P={A,D,E},P={B,C,F)

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

2122

(3)区分P1油于A,E输入。到终态，而D输入0不到终态，所以D与A,E可以区分，有Pn={A,E},PI2={D}。

(4)由于口儿0)=8下任。)=匕而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,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的引线引向与其等价的状态A,有图(a2)。(DFA的最小化，也可看作将上表中的B全部替换为A,

然后删除B所在的行。)

口

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

<b):该图已经是DFA。下面将该DFA最小化:

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

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

2

P2i«{4},P22-{1,2,3,5)。

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

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

(9)区分P；由'于F(1$)=F(5,b)=4,即F(1,a)=1,F(5,a)=5,所以1,5等价。

221

(10)区分Pzzz:由于F(2,a)=1属于P221,而F(3,a)=3属于P222,所以2,3可区分。P222区分为Pz22i{2},P2222{3}<)

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

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

(b1)最小化的DFA

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

语言的正则文法。

解：根据题意，DFA所对应的正规式应为：(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最小化后有:

对应的正规文法为：

G[A]：

A1C|0A|£

COA

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

解：把原正规式的每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[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出发任何输入串都不能到达状态E和F,所以，状态E,F为多余的状态，不予考虑。这样，可以

写出文法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的终态，其他是非终态，可将状态集分成两个子集：

12

P=<1.2.3.6.7}.P={4.5}

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

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

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

等价。所以P11可区分为：

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

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)为所求的正规式。

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

解：

(1)因为6,7是DFA的终态，其他是非终态，可将状态集分成两个子集：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