Diffrence between DFA and NFA

DFA:

  1. DFA” stands for “Deterministic Finite Automata.
  2. In DFA the next possible state is distinctly set.
  3. DFA cannot use empty string transition.
  4. Backtracking is allowed in DFA.
  5. DFA requires more space.

NFA:

  1. NFA” stands for “Nondeterministic Finite Automata.”
  2. In NFA each pair of state and input symbol can have many possible next states.
  3. NFA can use empty string transition.
  4.  NFA requires less space.
  5. Backtracking may or may not be allowed in NFA.

but in term of power, DFA is equivalent to NFA.

If there are n states in NFA then equivalent DFA may have at most 2n states.

0Comment