convert NFA to DFA

compile

---

Question

solution :

A = $\varepsilon-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\}$ = $\varepsilon-closure(3)$ = $\{0,3\}$
H = $move(E,b)$ = $\{\}$
I = $move(F,a)$ = $\{1,3\}$ =$\varepsilon-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\}$ =$\varepsilon-closure(2,3)$ = $\{0,2,3\}$
P = $move(K,b)$ = $\{0,2\}$ = F
Q = $move(O,a)$ = $\{1,2,3\}$ =$\varepsilon-closure(1,2,3)$ = $\{0,1,2,3\}$
R = $move(O,b)$ = $\{\}$
S = $move(O,a)$ = $\{1,2,3\}$ =$\varepsilon-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\}$

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 :

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\}$

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 :