Differentiate between NFA and DFA

Differences between NFA and DFA

S.no.TitleNFADFA
1.AbbreviationNon deterministic finite automataDeterministic finite automata
2.PurposeIn NFA, The Transition function maps on at least one state for valid input symbol.In DFA, The Transition function maps on at most one state for valid input symbol.
3.Powersamesame
4.Transition Functionδ : Q X Σ –> 2 ^ Q.δ : Q X Σ –> Q.
5.Time ComplexityThe time needed for executing an input string is moreThe time needed for executing an input string is less.
6SupremacyAll DFAs are NFA but not all NFAs are DFAAll DFAs are NFA.

Leave a Reply