PadhaikoAll subjects

Past exam question: 2082 Kartik (Back), Q2(a)(i)

Theory of Computation · 2 marks

Open in the Padhaiko app

Topic: Finite State Machines & DFA Design

Question

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:

ParameterDeterministic 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 TransitionsNot permitted (no spontaneous moves without reading an input)Permitted in -NFA ()
Execution PathUnique, deterministic single path for every input stringTree of concurrent possible execution paths
Acceptance CriterionAccepts if the single path ends in an accept state Accepts if at least one path ends in an accept state
Implementation / BacktrackingTrivially implemented in hardware/software with time and no backtrackingRequires subset tracking or backtracking during simulation
State ComplexityMay require up to states for an equivalent -state NFAOften 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.

All past exam questions for Theory of Computation