# Non-Deterministic finite Automata

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 q0 and the next input symbol is 1, then the next state will be either :

1) q0 2) q1

Thus, the move from q0 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, Σ, δ, q0, 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 2Q

q0 = q0 ϵ 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,

({q0, q1, q2}, {0, 1},δ ,{q2})

where, the transition function δ is given below in table