Difference between DFA and NFA 

Slno Similarities
1.

Both are transition functions of automata.

2. Both have same power.
3.
Slno DFA NFA/NDFA
1. Stands for “Deterministic Finite Automata”. Stands for “Non-deterministic Finite Automata”.
2. No empty string transitions occurs in DFA. Empty string transitions may also possible.
3. Backtracking is allowed in DFA. In NDFA, it is not always possible to backtrack.
4. DFA requires more space. NDFA requires less space.
5. All DFA are NFA. All NFA are not DFA.
6. The time needed for executing an input string in DFA is less. The time needed for executing an input string in NFA is more.
7. For every symbol of the alphabet, there is only one state transition in DFA. For every symbol of the alphabet, there may be no or multiple state transition in NFA.
8. DFA is comparatively more difficult to construct. NFA is comparatively easier to construct.
9.

In DFA we cannot move from one state to another without consuming a symbol.

NDFA allows € (null) as the second argument of the transition function i.e. the NDFA can make a transition without consuming an input symbol.

10.

When processing a string in DFA , there is always a unique state to go next when each character is read. It is because for each state in DFA , there is exactly one state that corresponds to each character being read.

For each input symbol, the transition can be to multiple next states. In NDFA several choices may exist for the next state. We can move to more than one states.

 2,378 total views,  3 views today


0 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.