构造下列正规式相应的DFA:(1) 1(0|1)* 101(2) 1(1010* | 1(010)* 1)* (3) a((a|b)*|ab*a)* b(4) b((ab)* | bb)* ab
构造下列正规式相应的DFA:
(1) 1(0|1)* 101
(2) 1(1010* | 1(010)* 1)*
(3) a((a|b)*|ab*a)* b
(4) b((ab)* | bb)* ab
题目解答
答案
解:
(1)1(0|1)* 101对应的NFA为
下表由子集法将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] |
(2)1(1010* | 1(010)* 1)* 0对应的NFA为
下表由子集法将NFA转换为DFA:
I | I0 = ε-closure(MoveTo(I,0)) | I1 = ε-closure(MoveTo(I,1)) |
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] |
(3)a((a|b)*|ab*a)* b (略)
(4)b((ab)* | bb)* ab (略)
解析
对于每个给定的正规式，首先构造相应的NFA。NFA的构造基于正规式的结构，使用状态转换图来表示。
步骤 2：将NFA转换为DFA
使用子集构造法将NFA转换为DFA。子集构造法的基本思想是将NFA的状态集作为DFA的状态，通过计算每个状态集在输入符号下的闭包来确定DFA的状态转换。
步骤 3：简化DFA
如果需要，可以对DFA进行简化，去除不可达状态和等价状态，以得到最小化DFA。