**Difference between DFA and NFA**

SR.NO. | DFA | NFA |
---|---|---|

1 | DFA stands for Deterministic Finite Automata | NFA stands for Non-Deterministic Automata |

2 | More, if NFA contains Q states then the corresponding DFA will have <= 2^{Q} states. | NFA has fever number of states |

3 | DFA cannot use Empty String transition | NFA can use Empty String transition. |

4 | DFA is as powerful as an NFA | NFA is as powerful as an DFA |

5 | Difficult to design as transitions are deterministic | Easy to design due to non-determinism. |

6 | All DFA are NFA | Not all NFA are DFA |

7 | The time needed for executing an input string is less | Time needed for executing an input string is more. |

8 | It is easy to find whether w ϵ L as transitions are deterministic. | It is difficult to find whether w ϵ L as there are several paths. |

9 | In DFA, the next possible state is distinctly set. | In NFA, each pair of state and input symbol can have many possible next states. |

10 | DFA can be understood as one machine | NFA can be understood as multiple little machine computing at the same time. |

11 | DFA is more difficult to construct | NFA is easier to construct |

**Deterministic finite Automata**

The word “deterministic” refers to the fact that the transition is deterministic. There is only one state to which an automaton can transit from the current state each input. The word “finite” implies that number of state are finite. A finite automata consists of five parts:

- 1. A finite set of states, represented as Q.
- 2. A finite set of alphabet, represented as Σ.
- 3. An initial state, represented as
**q**_{0}. - A set of accepting states. An accepting state or final state is for ‘Yes’ answer. It is a subset of Q and is represented as F.
- F ⊆ Q
- 5. A next state function or a transition function. Next state depends on the current state and the current input. It is a function from Q X Σ to Q. It is repesented as δ .

Finite automata,

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

Q is a set of states.

Σ is a set of alphabet.**q**_{0} ϵ Q is the initial state

F ⊆ Q is the set final states, and δ, the transition function, is a function from Q X Σ to Q.

**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 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}})

**Recommended:**

- Introduction to Finite Automata
- Deterministic Finite Automata (DFA)
- Number of 1’s is a multiple of 3 on {0,1} using DFA
- Number of 1’s is not multiple of 3 on {0,1} using DFA
- 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