Home »
Theory of Computation
Difference between DFA and NDFA | TOC
TOC | DFA vs NDFA: In this article, we are going to learn about the DFA, NDFA and the differences between DFA and NDFA in TOC.
Submitted by Mahak Jain, on November 12, 2018
DFA stands for Deterministic Finite Automata and NDFA stands for Non-Deterministic Finite Automata.
Read more: Deterministic Finite Automata (DFA)
Difference between DFA and NDFA
| DFA | NDFA |
| It stands for deterministic finite automata. |
It stands for non-deterministic finite automata. |
| The transition takes place from a state to a single particular state for each input symbol. |
For each input symbol, the transition can be to multiple next states. |
| There are no empty string transitions in DFA. |
Empty string transitions are also permitted. |
| Backtracking is allowed in DFA. |
In NDFA, it is not always possible to backtrack. |
| DFA requires more space. |
NDFA requires less space. |
| There no such randomness as the transition can be determined in DFA. |
There is much more randomness as the transition from one state to other cannot be determined in this. |
| Ex: δ: Q × ∑ → Q |
Ex: δ: Q × ∑ → 2Q |
 |
 |