The finite automaton or finite automata theory has several classes that include the Deterministic Finite Automata (DFA) and the Nondeterministic Finite Automata (NFA). These two classes are transition functions of finite automata or finite automata and they have some significant differences those are completely distinguish the behavior of the finite auotmata. Here two separate tables those are clearly explained the difference between the DFA and NFA and compare the performance of DFA and NFA on the behalf of various fields;
Difference between Deterministic Finite Automata and the Non deterministic Finite Automata ((DFA Vs NFA):
S. No. | DFA | NFA |
1. | For Every symbol of the alphabet, there is only one state transition in DFA. | We do not need to specify how does the NFA react according to some symbol. |
2. | DFA cannot use Empty String transition. | NFA can use Empty String transition.
|
3. | DFA can be understood as one machine. | NFA can be understood as multiple little machines computing at the same time.
|
4. | DFA will reject the string if it end at other than accepting state. | If all of the branches of NFA dies or rejects the string, we can say that NFA reject the string. |
5. | Backtracking is allowed in DFA. | Backtracking is not always allowed in NFA. |
6. | DFA can be understood as one machine. | NFA can be understood as multiple little machines computing at the same time. |
7. | DFA will reject the string if it end at other than accepting or final state. | If all of the branches of NFA dies or rejects the string, we can say that NFA reject the string. |
8. | DFA is more difficult to construct. | NFA is easier to construct. |
9. |
Also check: Complexity class in DAA
Comparison between Deterministic Finite Automata (DFA) and the Nondeterministic Finite Automata (NFA):
S. No. | Title | NFA | DFA |
1. | Power | Same | Same |
2. | Supremacy |
Not all NFA are DFA. |
All DFA are NFA |
3. |
Transition Function |
Maps Q → (∑∪{λ}→2Q), the number of next states is zero or one or more. |
Q × ∑→Q, the number of next states is exactly one |
4. | Time complexity |
The time needed for executing an input string is more as compare to DFA. |
The time needed for executing an input string is less as compare to NFA. |
5. | Space | Less space requires. | More space requires. |
Also check: context-free grammar examples
hi, i am archana
this website is very good!!!!!!
Hello Archana, Thanks for your appreciation.
yes archana this is very gud website and i am also planning a website like this we should appriciate the team
why dfa does not accept same latter transition ?
please explain with example.
Simple and very useful
I want the difference between finite automata, transition state, NFA….
what you mean by the difference between nfa state and dfa state.Actually i cant understand the difference of the states…??????????????????????????
at first, we should know something about the automata theory.so automata theory is the study of abstract machines and automata.we can solve some computational problems from this particular theory. automata theory has several clases. here two of them, DFA and NFA are described beautifully. So we should know some more classes of automata theory as it is very important subject.
hi m Noveen!
want to clear about the machines of both dfa and nfa . The machines are rather confusing. i alwys mix them.
nice