Home › GATE CSE › computerscience › Theory of Computation › Which is a key difference between a DFA and an N…
Which is a key difference between a DFA and an NFA (Non-deterministic Finite Automaton)?
ADFAs accept regular languages; NFAs do NOT
BNFA transitions can lead to a SET of next states
CDFAs have more states than NFAs for every language
DNFAs cannot be converted to DFAs
Answer & Solution
Correct answer: B. NFA transitions can lead to a SET of next states
1. NFA transition function: $\delta_N : Q \times (\Sigma \cup \{\varepsilon\}) \to 2^Q$ — returns a SET of possible next states.
2. From a given state with a given input, the NFA may have multiple choices (or none) of where to go.
3. ACCEPTANCE: NFA accepts $w$ if SOME path through the computation ends in an accepting state.
4. EQUIVALENCE: every NFA can be converted to a DFA (subset/powerset construction) that recognises the same language. So DFAs and NFAs recognise the SAME class of languages: regular languages. Option A is wrong.
5. State blow-up: the DFA equivalent can have UP TO $2^n$ states where the NFA has $n$ states (option C wrong in general). Option D contradicts the subset construction.
_Source: Jeff Erickson, "Models of Computation", §2.6 (Nondeterministic Finite Automata)._
Related questions
Which class of grammars generates ALL recursively enumerable languages?What is a LEFTMOST DERIVATION?Which of the following languages is CONTEXT-FREE?Consider the grammar $S \to (S) \mid SS \mid \varepsilon$. The language generated isEvery regular language is also context-free. The PROOF construction isThe CYK algorithm parses a CFG in CNF. Its time complexity for a string of length $n$ isA LEFT-RECURSIVE rule in a CFG has the form $A \to A\alpha$ for some non-empty $\alpha$. WContext-free languages are CLOSED under which of the following operations?