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 |