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

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

Comments and Discussions!

Load comments ↻

Copyright © 2024 www.includehelp.com. All rights reserved.