Subject: Compiler Design
Semester: BE Computer Sem-7
Question: Difference Between Deterministic Finite Automata (DFA) and Nondeterministic Finite Automata (NFA).
Semester: BE Computer Sem-7
Question: Difference Between Deterministic Finite Automata (DFA) and Nondeterministic Finite Automata (NFA).
| DFA | NFA |
|---|---|
| DFA stands for Deterministic Finite Automata | NFA stands for Nondeterministic Finite Automata |
| For each symbolic representation of the alphabet, there is only one state transition in DFA | No need to specify how does the NFA react according to some symbol |
| DFA cannot use Empty String transition | NFA can use Empty String transition |
| DFA can be understood as one machine | NFA can be understood as multiple little machines computing at the same time |
| In DFA, the next possible state is distinctly set | In NFA, each pair of state and input symbol can have many possible next states |
| DFA is more difficult to construct | NFA is easier to construct |
| DFA rejects the string in case it terminates in a state that is different from the accepting state | NFA rejects the string in the event of all branches dying or refusing the string |
| Time needed for executing an input string is less | Time needed for executing an input string is more |
| All DFA are NFA | Not all NFA are DFA |
| DFA requires more space | NFA requires less space then DFA |
