Theory of Automata

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 2n.

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

 

Help Other’s By Sharing…

Contact Us

Burewala, Vehari, Punjab, Pakistan

cstaleem1@gmail.com

Website: CStaleem.com

Pin It on Pinterest