Past exam question: 2082 Kartik (Back), Q2(a)(i)
Open in the Padhaiko appQuestion
Differentiate between DFA and NFA.
Solution
Core Structural and Operational Differences: Deterministic Finite Automata (DFA) and Nondeterministic Finite Automata (NFA) are both acceptors of regular languages, but differ in transition mechanics:
| Parameter | Deterministic Finite Automaton (DFA) | Nondeterministic Finite Automaton (NFA) |
|---|---|---|
| Transition Function | (maps to exactly one state) | (maps to a set of zero, one, or more states) |
| Epsilon Transitions | Not permitted (no spontaneous moves without reading an input) | Permitted in -NFA () |
| Execution Path | Unique, deterministic single path for every input string | Tree of concurrent possible execution paths |
| Acceptance Criterion | Accepts if the single path ends in an accept state | Accepts if at least one path ends in an accept state |
| Implementation / Backtracking | Trivially implemented in hardware/software with time and no backtracking | Requires subset tracking or backtracking during simulation |
| State Complexity | May require up to states for an equivalent -state NFA | Often exponentially more compact ( states) |
Answer:
A DFA has a unique transition for each state and input symbol, requiring no guessing or backtracking. An NFA maps to a set of states and can have -transitions. Both accept the exact same class of regular languages.