# Non Deterministic Finite Automata

**Non Deterministic Finite Automata** has great importance in the theory of computation. As we learnt in the previous article, i.e., in **Deterministic Finite Automata**, the next input symbol is determined in the next step. But, in a **Non Deterministic Finite Automata**, there are several choices may exist at any point in the next state. So, every Deterministic Finite Automata is automatically a Non Deterministic Finite Automata. NFAs are used in the implementation of regular expressions.

In **NFA**, each state can have zero, one, two, or more transitions corresponding to a particular input symbol. It can also have an empty **(ε)** transition, where NFA can change state without consuming an input symbol.

## Features of NFA

- NFA can perform parallel computation, multiple processes can be running concurrently.
- It can permit
**null**or**empty (ε)**string transition. - In a NFA, a state may have zero, one or many exciting arrows for each alphabet symbol. It has a choice of where to move to the next state.
- We can easily convert every NFA into an equivalent DFA.
- It is easy to understand and functionality may be easier than a DFA.

## Formal definition of NFA

Non Deterministic Finite Automata also has 5 tuples.

### (Q, ∑, δ, q0, F)

**Q** - It has a finite set of states.

**∑** - Alphabet of input symbols.

**δ** - A transition function that takes as argument a state and a symbol and returns a state.

##### δ: Q × (Σ ∪ {∈}) -> p(Q)

where, P(Q) is the power set of Q.

**q0** - A start state.

**F** - A set of final or accepting states.

A string is accepted by a NFA if **δ(q0, w)** contains at least one final state.

## Represent NFA with Transition Table

Here is an example of an NFA using a transition table and a graph.

0 |
1 |
ε |
||||

q0 |
{q0} | {q0,q1} | ∅ | |||

q1 |
{q2} | {q2} | {q2} | |||

q2 |
{q3} | {q3} | ∅ | |||

q3 |
∅ | ∅ | ∅ |

NFA transition diagram of above transition table.

Deterministic Finite Automata

Moore and Mealy Machines