# Introduction to NFA

NFA means non-deterministic finite automata.

The main difference between NFA and DFA is that we can move to > 1 states on single input.

We basically use NFA in backtracking and exhaustive search.

Following are the parameters of NFA:

Symbol | Description |
---|---|

Q | Set of finite states |

Σ | Input alphabet |

q0 | Start State |

δ | Transition Function: δ : Q X Σ -> 2^{Q} |

F | Final State |

Now we will understand using one example:

#### End with 'a'

L = {a, aa, ab, ...}

And the above property is true because the δ of DFA is ⊆ δ of DFA

As δ : Q X Σ -> 2

**Note: 1**Every DFA is NFA but vice-versa is not true.And the above property is true because the δ of DFA is ⊆ δ of DFA

As δ : Q X Σ -> 2

^{Q}⊇ Q X Σ -> Q**Note 2:**We do not have dead states in NFA**Note 3:**NFA and DFA both are equivalant in power (This is because "Every DFA is NFA" and "We can convert NFA to DFA")