Difference Between DFA and NFA
There is not too much difference in DFA and NFA because they both accept the regular languages. But the basic difference in DFA and NFA is given below.
DFA Vs. NFA
SR.NO. | DFA | NFA |
1 | DFA stands for Deterministic Finite Automata. | NFA stands for Nondeterministic Finite Automata. |
2 | For each sigma value (0, 1…n) there must be a provided path from each state. | For each sigma value (0, 1…n) there is no need to specify path from each state |
3 | As DFA provide a path for each input, that’s why all digital computers are deterministic. | As NFA does not provide a path for each input, that’s why NFA not use in digital computers. |
4 | Multiple choices are not available corresponding to an output. | Multiple choices are available corresponding to an output. |
5 | DFA cannot use Empty String
(Epsilon) transition. |
NFA can use Empty String (Epsilon) transition. |
6 | DFA is more difficult to construct and understand. | NFA is easier to construct and understand. |
7 | All DFA are NFA. | Not all NFA are DFA. |
8 | DFA requires more space. Because it has normally more states. | NFA requires less space then DFA. Because it has normally less states |
Note: While conversion of NFA to DFA, If NFA maximum states are n Then DFA maximum number of states will be 2^{n}. |
||
9 | Dead State cannot used in NFA | Dead State is used in NFA |
10 | Trap State is used in DFA | Trap State is not used in DFA |