编译原理第4章答案
发布时间：2023-04-07 09:02:59 来源：文档文库
小
中
大
字号：
编译原理习题解答 页1/1 第四章 词法分析
1．构造下列正规式相应的DFA：
* (1 1(0|1101 * * * (2 1(1010| 1(01010 ***(3 a((a|b|aba b * * (4 b((ab| bbab 解：
* (11(0|1101对应的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
* * * (21(1010| 1(01010对应的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：
编译原理习题解答 页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 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
(3a((a|b|aba b (略
* * (4b((ab| bbab (略
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 