Mathematical Foundation of Computer Science

DHARM

196 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

· From state {q 0 , q 2 } next reachable states are {q 0 , q 1 , q 3 } and {q 0 } on symbol 0 and 1.

Among them {q 0 , q 1 , q 3 } state is the new reachable state hence find transitions from

state {q 0 , q 1 , q 3 } only.

· From state {q 0 , q 1 , q 3 } next reachable states are {q 0 , q 1 , q 3 } and {q 0 , q 2 , q 3 } on symbol 0

and 1. From them {q 0 , q 2 , q 3 } is the new reachable state.

· From state {q 0 , q 2 , q 3 } next reachable states are {q 0 , q 1 , q 3 } and {q 0 , q 3 } on symbol 0 and

1, where {q 0 , q 3 } is only the new reachable state.

· From state {q 0 , q 3 } next reachable states are repeated states {q 0 , q 1 , q 3 } and {q 0 , q 3 }.

Hence, procedure stops.

Hence, we obtain a DFA M which is shown in Fig. 8.3.

{, }qq 01

{, }qq 02

{,qq 02 ,q 3 }

{,qq 02 ,q 3 }

{, }qq 03

{}q 0

1

0

0

1

1

0

0

0

1

1

0

1

Fig. 8.3 M.
From DFA state diagram we find that there is one and only one transition defined from
each state over each input symbol hence, finite automaton is deterministic finite automaton.
Example 8.1. Construct a DFA from given NFA N = ({q 0 , q 1 , q 2 , q 3 }, {0, 1}, δ, {q 0 }, {q 1 , q 3 }), where
transition functions δ are shown in the state diagram in Fig. 8.4.

0

1

0

1

0, 1

1, 0

1

q 0

q 3

q 2

q 1

Fig. 8.4 N.