编译原理第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

1 1 0 1

0 1 2 3 4

1

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

I I0 = ε-closure(MoveTo(I,0)) I1 = ε-closure(MoveTo(I,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]

0 0

1 1 0 1

A B C D E

1

1

0,1

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

ε

ε

1 1 0 1 0 1 0

0 1 2 3 4 5 6 1

0

1 ε ε

0

0 1

9

7 8

ε

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

I I

= ε-closure(MoveTo(I,0)) I

1 = ε-closure(MoveTo(I,1)) 0

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] I[1,2,5,6,7]

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

I[1,2,5,6,7] L[3,8,10] I[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]

1 L

1 1 1

1

0

0

1 1 0 1 0

B I K A D E F M

0

0 1

1 0

0 0

C 1 1 G H J

0

1

0 1

N P O

0

(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图如下 0

1

0 x y

0

1

0 z

0

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

I I

= ε-closure(MoveTo(I,0)) I

1 = ε-closure(MoveTo(I,1)) 0

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]

1 1 0

0 0 0 0

A B C D E F

0 1 1

1

下面将该 DFA 最小化：

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

1 2 (2) 区分 P :由于 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,

2

而 D， E 不等价（见下步） ，从而 B 与 C， F 可以区分。有 P ={C,F},P ={B}。

21 22

(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 1 1 0

0 0 0

A B D E F

0

3.将图确定化：

0 V 0

0

0，1

1

0， 1 S Q Z

1

1 U 1

图

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

I I0 = ε-closure(MoveTo(I,0)) I1 = ε-closure(MoveTo(I,1))

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

B[Q,V] D[V,Z] C[Q,U]

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

D[V,Z] G[Z] G[Z]

E[V] G[Z]

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

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

C 0

E 0

1 1

A 1 F 1 G 0， 1

0 0 0， 1

0

B D

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

b b

0

2

3

a

a

a,b b

a

0 1

a a b

a

1 4 5

b

a

a b

(a) (b)

解：

(a):

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

I Ia = ε-closure(MoveTo(I,a)) Ib = ε-closure(MoveTo(I,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 所在的行。）

B a a

a

b

C

A b A

b

C

a

a

（ a1）确定化的 DFA （ a2）最小化的 DFA

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

(6) 首先将它的状态集分成两个子集： P1={0},P2={1,2,3,4,5} (7) 区分 P ：由于 F(4,a)=0 属于终态集，而其他状态输入 a 后都是非终态集，所以区分 P 如下：

2 2

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) 区分 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 属于 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) 。

b b

0

2

3

b a

a

a a

1 b 4

a b

(b1) 最小化的 DFA

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

语言的正则文法。

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

ε

1

1 0

0 2

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

I I

= ε-closure(MoveTo(I,0)) I

1 = ε-closure(MoveTo(I,1))

0

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

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

C[1] B[0,2]

1

A 1

C 0

0

B

0

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

0

A 1 C

0

对应的正规文法为：

G[A]：

A1C|0A | ε

C0A

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

θ =dd* |dd * .dd* |.dd * |dd * e(s| ε )dd * |e(s| ε )dd * |.dd * e(s| ε )dd * |dd * .dd * e(s| ε )dd*