内容发布更新时间 : 2024/11/14 12:38:11星期一 下面是文章的全部内容请认真阅读。

第四章词法分析

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 1 2 0 3 1 表由子集法4 转换为

将NFADFA：

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

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

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

**0 1 D 1 1 E 0,1 ε ε 0 1 1 1 2 0 3 1 ε 0 7 0 8 1 ε 换为DFA：

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

0 1 0 下

4 5 ε 6 10 表由

子集法将NFA转

1 9 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] O[4] P[2,5] P[2,5] N[3] 1 1 0 C 1 P 1 1 1 1 1 D 0 E 1 F 0 G 1 0 H B[1,6] 1 L 1 I 0 0 K 1 0 0 J 0 1 0 A B M 0 O 0 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图如下 0

1 0 下表由子集法将DFA： x NFA转换为y 0 1 I I0=ε-closure(MoveTo(I,0)) 0 z A[x] B[z] 0 B[z] C[x,z] C[x,z] C[x,z] *

*

I1=ε-closure(MoveTo(I,1)) A[x] D[y] E[x,y]