首页 > 编译原理第4章答案

编译原理第4章答案

发布时间：2023-02-25 15:00:23 来源：文档文库

小中大

字号：

手机查看

第四章词法分析
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
1 0
1 1
下表由子集法将NFA转换为DFA：
I
I0 = ε-closure(MoveTo(I,0
I1 = ε-closure(MoveTo(I,1
1
2
0
3
1
4

A[0] B[1] C[1,2] D[1,3] E[1,4]

B[1] D[1,3] B[1] B[1]
B[1] C[1,2] C[1,2] E[1,4] B[1]

0
1 A
B
1
C
1

0,1
* * * 0
0
D 1
1
E

(21(1010| 1(01010对应的NFA为

ε ε
1 0
1
1
0 7
8
ε
下表由子集法将NFA转换为DFA：
I
I0 = ε-closure(MoveTo(I,0
I1 = 1
2
0
3
ε
0
1
9
1
4
0
5 ε
1
6
0
10

ε-closure(MoveTo(I,1
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]
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]
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]

本文来源：https://www.2haoxitong.net/k/doc/4b9b3004091c59eef8c75fbfc77da26924c5964f.html