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 :
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}
new group again:
G1={0}
G4={3,4}
G5={1}
G6={2}
so the minimized DFA is :
question
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}
the minimized dfa is :