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.
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.
dhanyawad
ReplyDelete