编译原理习题解答 页6/6
(1) 生成的3型文法是：
G[S]：S?aS|ε
(2) 生成的2型文法是：
G[S]: S?AB A?aA|a B?bB|b 生成的3型文法是： G[S]： S?aP P?aP|bD D?bD|ε (3) 生成的2型文法是：
G[S]: S?ABC A?aA|ε B?bB|ε C->cC|ε
生成的3型方法是： G[S]： A?aA|bB|cC|ε B?bB|cC|ε C?cC|ε
编译原理习题解答 页7/7
第四章 词法分析
1．构造下列正规式相应的DFA：
*
(1) 1(0|1)101
* * *
(2) 1(1010| 1(010)1)0
***
(3) a((a|b)|aba) 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] I0 = ε-closure(MoveTo(I,0)) I1 = ε-closure(MoveTo(I,1)) B[1] C[1,2] C[1,2] E[1,4] B[1] 1 2 0 3 1 4
0
A 1 B 1 0 C 1 1 0,1 0 D 1 E
* * *
(2)1(1010| 1(010)1)0对应的NFA为
ε ε 0 1 1 1 2 1 0 0 3 1 4 0 5 ε 1 6 0 10 ε 0 7 8 1 9 ε
下表由子集法将NFA转换为DFA：
编译原理习题解答 页8/8 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 1 0 I 1 H 0 L 0 K 0 J 0 0 M
A 1 B 0 C 1 1 1 P 0 O 0 1 N
(3)a((a|b)|aba) 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
***
编译原理习题解答 页9/9
下表由子集法将NFA转换为DFA：
I A[x] B[z] C[x,z] D[y] E[x,y] F[x,y,z]
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
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 编译原理习题解答 页10/10
解：下表由子集法将NFA转换为DFA： I A[S] B[Q,V] C[Q,U] D[V,Z] E[V] F[Q,U,Z] G[Z]
I0 = ε-closure(MoveTo(I,0)) B[Q,V] D[V,Z] E[V] G[Z] G[Z] D[V,Z] G[Z] C 1 A 1 0 D 0 1 F 1 0，1 E 0 I1 = ε-closure(MoveTo(I,1)) C[Q,U] C[Q,U] F[Q,U,Z] G[Z] F[Q,U,Z] G[Z] G 0，1
0 0 B
4.把图4.17的(a)和(b)分别确定化和最小化：
a
a,b
0 a
解： (a):
下表由子集法将NFA转换为DFA：
I A[0] B[0,1] C[1]
0 a a 1 a b b 2 b a b 4 b 5 a 3 a 1 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