Non-Determinstic finite automata can reside in multiple states at the same time. The concept of non -deterministic finite automata is being explained with the help of the transition diagram.

IF the automata is in the state q_{0} and the next input symbol is 1, then the next state will be either :

1) q_{0} 2) q_{1}

Thus, the move from q_{0} and the next input symbol is 1, cannot be determined uniquely. Such machines are called Non- deterministic automata.

– A Non- deterministic finite automata can be in several states at any time. Thus, NFA can guess about an input sequence.

– Every NFA can be converted into an equivalent DFA.

– An NFA can be designed with fewer states compare to its deterministic counterpart.

– Due to non-determinism, NFA take more time to recognize a string.

## Definition of NFA

A Non – deterministic finite Automata is a 5 tuple.

M = {Q, Σ, δ, **q**_{0}, F}

Q = A finite set states

Σ = A finite set of input

δ = A transition function from Q X Σ to the power set of Q i.e.to 2^{Q}

q_{0} = q_{0} ϵ Q is the start / initial state

F = F **⊆** Q is a set of final / accepting states.

The NFA, for table can be formally represented as,

({q_{0}, q_{1}, q_{2}}, {0, 1},δ ,{q_{2}})

where, the transition function δ is given below in table

**Recommended:**

- Introduction to Finite Automata
- DFA for Number of 1’s is even/odd and number of 0’s is even/odd
- DFA for number of 0’s divisible by five and 1’s divisible by 3
- DFA for All string of length at most five
- DFA for All strings ending with abb
- DFA for strings in which leftmost symbol differ from rightmost
- Design DFA that contain word ‘CAT’ using word ‘CHARIOT’
- Design DFA which accept a binary number divisible by 3
- Non-Deterministic finite Automata
- Design NFA to accept string containing the substring 0101
- Design NFA that accepts string ending with aab