Non Deterministic Finite State Machine examples

Non-Deterministic Finite State Machine:

If the automaton is in a state {q0} and the input symbol is 0, what will be the next state? From the figure, it is clear that the next state will be either {q0} 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.

A nondeterministic finite automaton (NDFA) is a 5-tuple (Q, ∑, δ, q0, F) where
(i) Q is a finite nonempty set of states
(ii) ∑ is a finite nonempty set of inputs
(iii) δ is the transition function mapping from Q x ∑ into 2Q which is the Power set of Q, the set of all subsets of Q.
(iv) q0 ∈ Q is the initial state, and
(v) F ⊆ Q is the set of final states.