Search This Blog

Monday, August 15, 2011

What is the difference between DFA and NFA?

What is the difference between DFA and NFA? 

Answer:

Difference between DFA and NFA

DFA stands for Deterministic Finite Automaton

NFA stands for Non-Deterministic Finite Automaton

•When processing a string in a DFA, there is
always a unique state to go next when each
character is read
•It is because for each state in DFA, there is
exactly one state that corresponds to each
character being read

•In an NFA, several choice (or no choice) may
exist for the next state
•Can move to more than 1 states, or nowhere
•Can move to a state without reading anything

or

Answer:
1. The transition function for nfa ie delta is multi valued where as for dfa it is single valued.
2. Checking membership is easy with dfa where as it is difficult for nfa
3. Construction of nfa is very easy where as for dfa it is difficult
4. Space required for dfa is more where for nfa it is less
5. Backtracking is allowed in dfa,but it is not possible in every casi in nfa.
6. For every input and output we can constuct dfa machine,but it is not possible to construct an nfa machine for every input and output.
7. There is only 1 final state in nfa but there can be more then 1 final state in dfa.