DFA
|
NFA
|
Stands for Deterministic Finite Automata. |
Stands for Nondeterministic Finite Automata. |
Only one transition for every input symbol at every state. |
May have several transitions for every input symbol at every state. |
It can not accept empty strings. |
It can accept empty strings. |
Backtracking is allowed in DFA. |
Backtracking is not allowed in NFA. |
Only one next state. |
The number of next states is zero or one or more. |
Difficult to construct. |
Very easier to construct. |
Sequential computation. |
Parallel Computation. |
More space required. |
Less space required. |
String accept it transit to final states. |
If at least one of all possible transition end in final states. |
It can be understood as one machine. |
It can be understood as several little machines that compute together. |
All DFA are NFA. |
Not all NFA is DFA. |
Require less time for execution |
Require more time for execution. |
![DFA DFA vs NFA](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgjAUF5M7SN0D8UljFl7l6xWUaz3pZCJMVC9h-exoSvWmWXbe3_7JjP069xbCFOAOXK846KzVJtXZSEwpf2mq4Ior0SXZBCj9RpBpSH-B2DjaERfp8BUjIVKFGD4F4_eCq12CM3w1eBuAaa/s1600-rw/dfa.jpg) |
Fig(1): DFA |
|
![NFA DFA Vs NFA](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg78E5pWB-tE5Tr8g8dljJumIgWa4ZuiXkWasH7Mu2f61IQ1w_eEqUpuCmd2getWBzCLbFt6FCYh3FNSBQfKCUJSF6F7lSjYmRwppbOgRDTg-T31V67szF-mi216mDLuhjH-wqqADlVCDMR/s200-rw/nfa.jpg) |
Fig(2): NFA |
|
Post a Comment