78 ~ Theory ofComputer Science
3.6 NONDETERMINISTIC FINITE STATE MACHINES
We explain the concept of nondeterministic finite automaton using a transition
diagram (Fig. 3.7).
o
1
~)~
O ----7
/
" ' - . . ,
/1
"tr
Fig. 3.7 Transition system representing nondeterministic automaton.
If the automaton is in a state {qa} and the input symbol is 0, what wii! be
the next state? From the figure it is clear that the next state will be either {qo}
or {qj}. Thus some moves of the machine cannot be determined uniquely by
the input symbol and the present state. Such machines are called
nondeterministic automata. the formal definition of which is now given.
Definition 3.5 A nondeterministic finite automaton (NDFA) is a 5-tuple
(Q, L. 0, qo, F), where
(i) Q is a finite nonempty set of states;
(ii) L is a finite nonempty set of inputs;
(iii) 0 is the transition function mapping from Q x L into 2
Q which is the
power set of Q, the set of all subsets of Q;
(iv) qo E Q is the initial state; and
(v) F ~ Q is the set of final states.
We note that the difference between the deterministic and nondeterministic
automata is only in 0. For deterministic automaton (DFA), the outcome is a
state, i.e. an element of Q; for nondeterministic automaton the outcome is a
subset of Q.
Consider, for example, the nondeterministic automaton whose transition
diagram is described by Fig. 3.8.
The sequence of states for the input string 0100 is given in Fig. 3.9. Hence,
8(qo, 0100) = {qo, q3' q4}
Since q4 is an accepting state. the input string 0100 will be accepted by
the nondeterministic automaton.