Ì Exam ple 1.3.1: Determine a deterministic Finite State Automaton
from the given Nondeterministic FSA.
M
q q
a b
q q
= ({ , }, { , }, , , { })
0
1
0
1
δ
with the state table diagram for δ given below.
δ
a
b
q 0
{q 0 , q 1 }
{q 1 }
q 1
∅
{q 0 , q 1 }
Solu tion
Let M
Q
q F
′ = ′
′ ′ ′
( , , , , )
Σ δ 0
be a determine. Finite state automaton (DFA),
where
Q′ = {[ ], [ ], [ , ], [ ]},
q
q
q q
0
1
0
1
∅
′
q 0 = [q 0 ]
and
F ′ = {[ ], [ , ]}
q
q q
1
0
1
Please remember that [ ] denotes a single state. Let us now proceed to
determine δ′ to be defined for the DFA.
δ′
a
b
[q 0 ]
[q 0 , q 1 ]
[q 1 ]
[q 1 ]
∅
[q 0 , q 1 ]
[q 0 ,q 1 ]
[q 0 ,q 1 ]
[q 0 ,q 1 ]
∅
∅
∅
It is to be noted that
δ′
=
([ , ], ) [ , ]
q q a
q q
0
1
0
1
since
δ
δ
δ
′
=
∪
=
∪ ∅
=
([ , ], )
( , )
( , )
{ , }
{ , }
q q a
q a
q a
q q
q q
0
1
0
1
0
1
1
1
and
δ′
=
([ , ], ) [ , ]
q q b
q q
0
1
0
1
since
δ
δ
δ
([ , ], )
( , )
( , )
{ } { , }
{ , }
q q b
q b
q b
q
q q
q q
0
1
0
1
1
0
1
0
1
=
∪
=
∪
=
76
Theory of Automata, Formal Languages and Computation