Difference between DFA and NFA

                                NFA

                          DFA

In Deterministic Finite Automata, exactly one state transition for every input symbol.

In NFA, for the same input symbol, there can be more than one next state symbol. Also, there can be epsilon transitions.

Conversion of Regular expression to DFA is complex.

A regular expression can be easily converted to NFA using Thomson’s construction.

DFA requires more memory for storing information.

NFA requires move computations to match Regular Expressions with input.

It is impossible to move next state without reading any symbol.

In NFA, we can move to the next state without reading any symbol.

EXAMPLE:

Construct a DFA that accepts all starting with “a”.

Q={A,B,D(dead state)}

∑ = {a,b}

L ={aa, ab, abb….aaab}

 

 

 

 

 

EXAMPLE:

Construct a NFA that accepts all starting with “a”.

Q={A,B}

∑ = {a,b}

L ={aa, ab, abb….aaab}

There is a concept of Dead state when a machine enters the dead state, there is no way to reach the final state. A machine may have several dead states but at most only one dead state is needed by a machine(DFA).

There is no concept of dead state.

No. of states : DFA ≥  NFA No. of states : DFA≥​ NFA

 

 

Contributor's Info

Created:
0Comment