DFA vs NFA: Key Differences and Their Applications in Automata Theory
☰Fullscreen
Table of Content:
DFA vs NDFA
The following table lists the differences between DFA and NDFA.
| DFA | NDFA |
|---|---|
| The transition from a state is to a single particular next state for each input symbol. Hence it is called deterministic. | The transition from a state can be to multiple next states for each input symbol. Hence it is called non-deterministic. |
| Empty string transitions are not seen in DFA. | NDFA permits empty string transitions. |
| Backtracking is allowed in DFA | In NDFA, backtracking is not always possible. |
| Requires more space. | Requires less space. |
| A string is accepted by a DFA, if it transits to a final state. | A string is accepted by a NDFA, if at least one of all possible transitions ends in a final state. |