编译原理第4章答案

第四章 词法分析

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

*

0

0 1 1 1 下表由子集法将NFA转换为DFA： I A[0] B[1] C[1,2] D[1,3] E[1,4] B[1] D[1,3] B[1] B[1] 1 2 0 3 1 4

I0 = ε-closure(MoveTo(I,0)) I1 = ε-closure(MoveTo(I,1)) B[1] C[1,2] C[1,2] E[1,4] B[1]

0

A

0,1

1 B 1 0 C 1 1 0 D 1 E

(2)1(1010* | 1(010)* 1)* 0对应的NFA为

4 0 5 ε 0 7 0 8 1 9 ε 下表由子集法将NFA转换为DFA：

1 6 0 10

ε ε 0 1 1 1 2 1 0 3 1 ε 编译原理习题解答 页2/2

I A[0] B[1,6] C[10] D[2,5,7] E[3,8] F[1,4,6,9] G[1,2,5,6,9,10] H[1,3,6,9,10] I[1,2,5,6,7] J[1,6,9,10] K[2,4,5,7] L[3,8,10] M[2,3,5,8] N[3] O[4] P[2,5] I0 = ε-closure(MoveTo(I,0)) C[10] E[3,8] G[1,2,5,6,9,10] H[1,3,6,9,10] J[1,6,9,10] L[3,8,10] J[1,6,9,10] M[2,3,5,8] N[3] P[2,5] N[3] 1 1 1 1 D 0 E 1 F 0 G 0 1 I1 = ε-closure(MoveTo(I,1)) B[1,6] D[2,5,7] B[1,6] F[1,4,6,9] D[2,5,7] I[1,2,5,6,7] K[2,4,5,7] I[1,2,5,6,7] D[2,5,7] B[1,6] F[1,4,6,9] F[1,4,6,9] O[4] B[1,6]

1 L 1 0 I 1 H 0 0 K 0 J 0 0

A 1 B 0 M

C 1 1 1 P 0 O 0 1 N

(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},构造相应的DFA。 解：根据题意有NFA图如下 1

x 0 0 z 0 0 1 0 y 编译原理习题解答 页3/3

下表由子集法将NFA转换为DFA：

I A[x] B[z] C[x,z] D[y] E[x,y]

I0 = ε-closure(MoveTo(I,0)) B[z] C[x,z] C[x,z] E[x,y] F[x,y,z] F[x,y,z] I1 = ε-closure(MoveTo(I,1)) A[x] D[y] E[x,y] A[x] E[x,y] 0 F[x,y,z] 1 A 0 B 0 1 C 0 1

D 1 0 E 0 1 F

下面将该DFA最小化：

(1) 首先将它的状态集分成两个子集：P1={A,D,E},P2={B,C,F}

(2) 区分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可以区分。有P21={C,F},P22={B}。

(3) 区分P1:由于A，E输入0到终态，而D输入0不到终态，所以D与A，E可以区分，有P11={A,E},P12={D}。 (4) 由于F(A,0)=B,F(E,0)=F,而B，F不等价，所以A，E可以区分。

(5) 综上所述，DFA可以区分为P={{A}，{B}，{D}，{E}，{C，F}}。所以最小化的DFA如下：

1 1 A 0 B 1 D 0 0 E 1 0 F 0

3.将图4.16确定化：

0 0，1 V 0 0 S Q 1 1 Z 0，1

1 U 图4.16

1 解：下表由子集法将NFA转换为DFA：

I A[S] B[Q,V] C[Q,U] D[V,Z] I0 = ε-closure(MoveTo(I,0)) B[Q,V] D[V,Z] E[V] G[Z] I1 = ε-closure(MoveTo(I,1)) C[Q,U] C[Q,U] F[Q,U,Z] G[Z] 编译原理习题解答 页4/4

E[V] F[Q,U,Z] G[Z]

G[Z] D[V,Z] G[Z] C 1 A 0 1 0 0 D 0 1 F 1 0，1 E F[Q,U,Z] G[Z] 0 G 0，1

B

4.把图4.17的(a)和(b)分别确定化和最小化：

解： (a):

下表由子集法将NFA转换为DFA：

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

a

a,b 0 a 1 0 a a 1 a b b 2 b a b 4 b 5 a 3 a b (a) (b)

Ia = ε-closure(MoveTo(I,a)) B[0,1] B[0,1] A[0] Ib = ε-closure(MoveTo(I,b)) C[1] C[1] 可得图（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所在的行。）

a A b a B b C a

a A b C a （a1）确定化的DFA （a2）最小化的DFA

（b）:该图已经是DFA。下面将该DFA最小化：

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

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

P21={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}。

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

编译原理习题解答 页5/5

(10) 区分P222:由于F(2,a)=1属于P221，而F(3,a)=3属于P222,所以2，3可区分。P222区分为P2221{2}，P2222{3}。 (11) 结论：该DFA的状态集可分为：P={ {0},{1,5},{2},{3},{4} },其中1,5等价。删去状态5，将原来

引向5的引线引向与其等价的状态1，有图(b1)。

0 a a 1 a b b 2 b 3 a b b a 4 (b1)最小化的DFA

5．构造一个DFA，它接收Σ={0，1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。然后再构造该语言的正则文法。

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

ε

1 0

0 1 2

下表由子集法将NFA转换为DFA：

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

1 A 1 C 0 B 0

0 I0 = ε-closure(MoveTo(I,0)) B[0,2] B[0,2] B[0,2] I1 = ε-closure(MoveTo(I,1)) C[1] C[1] 0

显然，A，B等价，所以将上述DFA最小化后有： 0

对应的正规文法为： G[A]：

A1C|0A|ε

C0A

6．设无符号数的正规式为θ：

A 1 0 C θ=dd|dd.dd|.dd|dde(s|ε)dd|e(s|ε)dd|.dde(s|ε)dd|dd.dde(s|ε)dd

************

化简θ,画出θ的DFA，其中d={0,1,2,…9},s={+,-}

解：把原正规式的每2，3项，4，5项，6，7项分别合并后化简有：

********

θ=dd|d.dd|de(s|ε)dd|d.dde(s|ε)dd

=dd|d.dd|(d|d.dd)e(s|ε)dd=(ε|d.|(d|d.dd)e(s|ε))dd

*

*

*

*

*

*

*

*

*

*

*

*

编译原理习题解答 页6/6

=(ε|d.|d(ε|.dd)e(s|ε))dd

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

****

0 d 1 . ε ε .

I B[1,7] C[5,6] D[2,6] E[7] F[6] G[3,4,7]

d e 5 ε 4 d ε 6 d 7 2 d s 3 下表由子集法将NFA转换为DFA：

Id =ε-closure(MoveTo(I,d)) B[1,7] E[7] G[3,4,7] E[7] E[7] G[3,4,7] Ie=ε C[5,6] C e d A d . -closure(MoveTo(I,e)) Is=ε-closure(MoveTo(I,s)) F[6] I.=ε-closure(MoveTo(I,.)) D[2,6] D[2,6] A[0,1,4,6] B[1,7] C[5,6] s d e E F d d B . D SaA|bQ AaA|bB|b BbD|aQ QaQ|bD|b DbB|aA EaB|bF FbD|aE|b

d G d 7．给文法G[S]：

构造相应的最小的DFA。

解：由于从S出发任何输入串都不能到达状态E和F，所以，状态E，F为多余的状态，不予考虑。这样，可以写出文法G[S]对应的NFA：

a

a S a b A b Z b Q a a b b b B b D 编译原理习题解答 页7/7

下表由子集法将NFA转换为DFA：

I 1[S] 2[A] 3[Q] 4[B,Z] 5[D,Z] 6[D] 7[B] 由上表可知：

(1)因为4，5是DFA的终态，其他是非终态，可将状态集分成两个子集： P1={1，2，3，6，7}，P2={4，5}

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

P11={1，6，7}，P12={2，3}

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

P111={1}，P112={6，7}

(4)查看P112={6，7}，由于输入a后为2，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等价,进而6，7也等价。

(7)删除上表中的第3，5，7行，并将剩余行中的3，5，7分别改为对应的等价状态为2，4，6有下表：

I 1[S] 2[A] 4[B,Z] 6[D] 这样可得最小化的DFA如下：

1 a b 2[A] 2[A] 2[A] 2[A] a 2 a a 6 b b b 4 Ia 2[A] 4[B,Z] 6[D] 6[D] Ib Ia = ε-closure(MoveTo(I,a)) 2[A] 2[A] 3[Q] 3[Q] 2[A] 2[A] 3[Q] Ib = ε-closure(MoveTo(I,b)) 3[Q] 4[B,Z] 5[D,Z] 6[D] 7[B] 7[B] 6[D] 编译原理习题解答 页8/8

8．给出下述文法所对应的正规式：

S0A|1B A1S|1 B0S|0 S=01|01S S=10|10S

有:S=01S|10S|01|10=(01|10)S|(01|10)=(01|10)(01|10) 即:(01|10)(01|10)为所求的正规式。

*

*

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

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

1 b a c 3 d c b 6 5 b

d a b b 7 b 解：

2 a 4 图 4.18

(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)=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) 由于状态5没有输入字符b,所以与1，2，3，4都不等价。

(3) 综上所述，上图DFA的状态可最细分解为：P={{1，2}，{3，4}，{5}，{6，7}}。

该DFA用正规式表示为： b 1 a c 3 d a b 6 5 b

b*a(c|da)*bb*

10．构造下述文法G[S]的自动机：

SA0 AA0|S1|0

该自动机是确定的吗？若不确定，则对它确定化。该自动机相应的语言是什么？

由于该文法的产生式SA0，AA0|S1中没有字符集VT的输入，所以不是确定的自动机。要将其他确定化，必须先用代入法得到它对应的正规式。把SA0代入产生式AS1有：A=A0|A01|0=A(0|01)|0=0(0|01)。代入SA0有该文法的正规式：0(0|01)0，所以，改写该文法为确定的自动机为：

*

*

解：

W 0 0 X 0 1 0 Z Y 编译原理习题解答 页9/9

由于状态A有3次输入0的重复输入，所以上图只是NFA，下面将它确定化：

下表由子集法将NFA转换为DFA：

I A[W] B[X] C[X,Y,Z] 由上表可知DFA为： I0 = ε-closure(MoveTo(I,0)) Ib = ε-closure(MoveTo(I,1)) B[X] C[X,Y,Z] C[X,Y,Z] B[X]

0 0 0 A B C 1