[关闭]
@weixin 2015-01-26T03:22:18.000000Z 字数 1741 阅读 1436

convert NFA to DFA

compile


Question

此处输入图片的描述

solution :

A = εclosure(0) = {0}
B = move(A,a) = {1}
C = move(A,b) = {}
E = move(B,a) = {2}
F = move(B,b) = {0,2}
G = move(E,b) = {3} = εclosure(3) = {0,3}
H = move(E,b) = {}
I = move(F,a) = {1,3} =εclosure(1,3) = {0,1,3}
J = move(F,b) = {}
K = move(G,a) = {1,2}
L = move(G,b) = {}
M = move(I,a) = {1,2} = K
N = move(I,b) = {0,2} = F
O = move(K,a) = {2,3} =εclosure(2,3) = {0,2,3}
P = move(K,b) = {0,2} = F
Q = move(O,a) = {1,2,3} =εclosure(1,2,3) = {0,1,2,3}
R = move(O,b) = {}
S = move(O,a) = {1,2,3} =εclosure(1,2,3) = {0,1,2,3} = Q
T = move(Q,b) = {0,2} = F

a little bit tedious, after drawing the pic, it looks like :
此处输入图片的描述

I re-schedule the node symbol in the pic, because in the above table, some symbol such as H and J is no use, and some others are duplciate.

question

minimize DFA :
dfa

solution

G1={0}
G2={1,2,3,5}

G2 a b
1 G2 -
2 G2 -
3 G2 G1
4 G2 G1

new Group
G1={0}
G3={1,2}
G4={3,4}

G3 a b
1 G3 -
2 G4 -

new group again:
G1={0}
G4={3,4}
G5={1}
G6={2}

G4 a b
3 G4 G1
2 G4 G1
G1 a b
0 G5 G6
2 G4 G1
G5 a b
1 G6 -
G6 a b
2 G4 -
G4 a b
3 G4 G1
2 G4 G1

so the minimized DFA is :
min dfa

question

dfa

solution

G1={4}
G2={0,1,2,3,5}

G2 a b
0 G2 G2
1 G2 G1
2 G2 G2
3 - -
5 G2 G2

new group
G1={4}
G3={2,0,5}
G4={1}
G5={3}

G3 a b
0 G5 G4
5 G3 G3
2 G3 G3

new group
G1={4}
G6={0}
G7={2,5}
G4={1}
G5={3}

G7 a b
2 G7 G7
5 G7 G7
G1 a b
4 G7 G7
G6 a b
0 G5 G4
G4 a b
1 G7 G1
G5 a b
3 - -

the minimized dfa is :
min dfa

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注