ADVERTISEMENT
ADVERTISEMENT

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

DFANDFA
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
TOC  | DFA TOC | NDFA
ADVERTISEMENT



ADVERTISEMENT



Comments and Discussions


ADVERTISEMENT

ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.