Table of Contents
hide
Difference between TOC in 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. |
Difference between TOC in
0 Comments