Mathematical Foundation of Computer Science

DHARM

198 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

· Reachable states from {q 2 } are : {q 3 } and {q 0 } that was earlier visited.

· Reachable states from {q 0 ,q 1 ,q 2 } :{q 1 , q 2 , q 3 } and {q 1 , q 2 }

· Reachable states from {q 1 ,q 2 } : {q 2 , q 3 } and {q 0 ,q 1 ,q 2 } a repeated state.

0

0

1

0

0

1 1

0

1

1

1

1

1

0 1

(^00)
0
q 1 q 2
q 3
F
{,q 1 q 3 }
q 0
{,q 1 q 2 }
{,q 2 q 3 } {,qq 13 ,}q 2
{,qq 03 ,}q 2
Fig. 8.6. M
For next state transitions take only new reachable state.
· Reachable states from {q 3 } are :ΦΦΦΦΦ and {q 3 } which is a repeated state.
· Reachable states from {q 1 , q 2 , q 3 } : {q 2 , q 3 } a repeated state and {q 0 , q 1 , q 2 }
· Reachable states from {q 2 , q 3 } : {q 3 } and {q 0 } both are repeated state.
· Reachable states from {q 0 , q 1 , q 2 } are: {q 1 , q 2 ,q 3 } and {q 1 ,q 2 } both are repeated state.
· Further, no new reachable state found hence process stop.
Thus, Fig. 8.6 shows the state diagram of final DFA.

8.3. FINITE AUTOMATA WITH ∈ MOVES

We have seen so far that a finite automaton of either deterministic or nondeterministic which
changes their state transitions only over known input symbols. Experience shows that there
might be a need of state transitions over no input symbol. It means, there are few states in the
finite automaton such that it skips between these states without consumption of any input
symbol. For this purpose, we introduce a new symbol epsilon (∈∈∈∈∈) that has a dimension and of
zero length, which is also called a null string.
Now we will discuss the nature of finite automata specifically, over null string (∈). Since
automata changes their state/s over null string so these transitions occurs over no symbol. In
other words, automata skip between states spontaneously. For example, automata is in
state {q} and its state changes to {q} over symbol ∈∈∈∈∈.