Nondeterministic finite automata and NFA to DFA conversion
Nondeterministic finite automata (NFA) are finite-state machines where a symbol can lead to many possible next states; every NFA can be converted to an equivalent deterministic finite automaton (DFA) by the subset-construction algorithm.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
An engineer uses finite automata when designing lexical analyzers, pattern-matchers, hardware/state controllers, or when proving properties of regular languages. Understanding Nondeterministic finite automata (NFA) and how to convert them to Deterministic finite automata (DFA) lets you implement regular-pattern recognisers efficiently and reason about correctness and complexity.
Key ideas
Σ is a finite input alphabet (set of symbols).
δ is the transition function: δ: Q × Σ → P(Q) (P(Q) means the power set of Q — the set of all subsets of Q). δ(q, a) gives the set of possible next states from q on symbol a.
q0 ∈ Q is the start state.
F ⊆ Q is the set of accepting (final) states. Note: this definition assumes no epsilon (ε) moves; ε-NFA is similar but allows ε-transitions and is a separate topic.
Deterministic finite automaton (DFA) — like an NFA but with exactly one next state for each state-symbol pair. Formally DFA is (Q', Σ, δ', q0', F') with δ': Q' × Σ → Q'. No nondeterminism.
Language of an automaton — the set of all strings over Σ that the automaton accepts. A string is accepted by an NFA if there exists at least one path (sequence of transitions) from q0 to some state in F labelled by the string.
Subset construction (powerset construction) — algorithm to convert any NFA N = (Q, Σ, δ, q0, F) into a DFA D = (Q_D, Σ, δ_D, q0_D, F_D) where:
- Q_D = P(Q) (each DFA state is a subset of N's states).
- q0_D = {q0} (or ε-closure of q0 if ε-transitions exist; not used here).
- For S ⊆ Q and a ∈ Σ, δ_D(S, a) = ⋃_{q ∈ S} δ(q, a).
- F_D = {S ∈ Q_D | S ∩ F ≠ ∅} (a subset is accepting if it contains at least one accepting NFA state).
Exact statement (theorem): For every NFA N there exists a DFA D constructed by the subset construction such that L(N) = L(D). Assumption: N has no ε-transitions; if ε-transitions exist, use ε-closure in construction.
Proof sketch (standard induction on input length): Base: empty string — DFA start subset is {q0} (i.e., the ε-closure of q0 when there are no ε-moves), so acceptance matches. Inductive step: assume after reading w both machines correspond; on reading a, DFA computes union of δ on states reachable in NFA after w, which equals NFA states reachable after wa. Therefore acceptance condition (contains accepting state) matches. (Give formal induction in exams.)
Complexity: If N has n states, the constructed DFA may have up to 2^n states (the whole power set). In practice many subsets are unreachable.
Dead state (sink) — a DFA state representing the empty subset ∅; if ∅ is reachable include it and make all its transitions point to ∅.
Diagrams to draw in an exam:
- For an NFA: draw one circle per state q0, q1, ...; put an incoming arrow (no source) to the start state q0; label accepting states with double circle; draw directed labeled edges q_i —a→ q_j for each transition (if δ(q_i,a) contains q_j). If multiple targets, draw multiple arrows from the same source with same label.
- For the DFA produced: draw circles labelled by subsets (e.g. {q0,q1}); mark {q0} as start; double-circle any subset containing an NFA final state; include arrow to ∅ if necessary. On paper, list transition table first and then draw only reachable subsets.
Formulas
N = (Q, Σ, δ, q0, F) — NFA definition; Q: set of states, Σ: alphabet, δ: Q × Σ → P(Q), q0 ∈ Q start, F ⊆ Q accept. Applies to NFAs without ε.
D = (Q_D, Σ, δ_D, q0_D, F_D) — DFA from subset construction; Q_D = P(Q), q0_D = {q0}, δ_D(S, a) = ⋃_{q∈S} δ(q, a), F_D = {S | S ∩ F ≠ ∅}. Applies to converting an NFA without ε-moves.
|Q_D| ≤ 2^{|Q|} — worst-case number of states in the constructed DFA from an N-state NFA. Applies when counting theoretical worst-case.
Accepted by NFA iff ∃ path q0 --w--> q_f with q_f ∈ F — definition of acceptance of string w by an NFA. (No units.)
Worked examples
Example 1 — convert a small NFA to DFA (step-by-step table and diagram description). Problem: Let N = (Q, Σ, δ, q0, F) with Q = {q0, q1, q2}, Σ = {a, b}, q0 start, F = {q2}, and δ defined:
- δ(q0, a) = {q0, q1}
- δ(q0, b) = {q0}
- δ(q1, b) = {q2}
- δ(q1, a) = ∅
- δ(q2, a) = ∅, δ(q2, b) = ∅ Interpretation in plain words: from q0 on 'a' the machine may stay in q0 or go to q1 (nondeterministic guess), q0 loops on 'b', and q1 goes to q2 on 'b'. This NFA accepts exactly the strings over {a,b} that end with the substring "ab".
Perform subset-construction:
- Start state: {q0}.
- Compute transitions from {q0}:
- on a: δ_D({q0}, a) = δ(q0,a) = {q0,q1}.
- on b: δ_D({q0}, b) = δ(q0,b) = {q0}.
- New subset {q0,q1}:
- on a: δ_D({q0,q1}, a) = δ(q0,a) ∪ δ(q1,a) = {q0,q1} ∪ ∅ = {q0,q1}.
- on b: δ_D({q0,q1}, b) = δ(q0,b) ∪ δ(q1,b) = {q0} ∪ {q2} = {q0,q2}.
- New subset {q0,q2}:
- on a: δ_D({q0,q2}, a) = δ(q0,a) ∪ δ(q2,a) = {q0,q1} ∪ ∅ = {q0,q1}.
- on b: δ_D({q0,q2}, b) = δ(q0,b) ∪ δ(q2,b) = {q0} ∪ ∅ = {q0}.
- No other new subsets; ∅ is not reachable here so no explicit dead state is required.
DFA states (reachable): {q0} (start), {q0,q1}, {q0,q2}. Accepting DFA states are those containing q2, so {q0,q2} is accepting. Transition table (write in exam):
- From {q0}: a → {q0,q1}, b → {q0}
- From {q0,q1}: a → {q0,q1}, b → {q0,q2}
- From {q0,q2}: a → {q0,q1}, b → {q0}
Diagram: draw three circles labelled {q0}, {q0,q1}, {q0,q2}; arrow from nothing to {q0}; double circle {q0,q2}; draw labelled arrows as above.
Conclusion: DFA accepts exactly the strings that end with the substring "ab". (Explain verbally in answer.)
Example 2 — proof-question style (short model answer): Prove L(N) = L(D) for subset construction. Model answer outline to write in an exam:
- State the NFA and constructed DFA precisely (include formulas for δ_D, q0_D, F_D).
- Prove direction 1 (if N accepts w then D accepts w): by induction on |w|. Base |w|=0: if ε accepted by N then q0 ∈ F, so {q0} contains accepting state → D accepts. Inductive step: assume for w, show for wa using δ_D definition and union property.
- Prove direction 2 (if D accepts w then N accepts w): similar induction but show that membership of some q_f ∈ S reached by D implies existence of a path in N leading to q_f.
- Conclude equality of languages.
(An examiner expects the full induction written out with clear base and step and referencing the union-of-transitions property.)
Common mistakes
- Not marking a DFA subset state as accepting when it contains any NFA final state.
- Forgetting or incorrectly handling the dead state (empty subset) when it becomes reachable.
- Drawing the DFA with unreachable subset-states and losing marks — always compute reachable subsets first.
- Mixing up ε-NFA rules with plain NFA (if ε-transitions appear, you must use ε-closure in the construction).
- Claiming the DFA always has exactly 2^n states (it may have fewer; 2^n is the worst-case upper bound).
For your exam
Kinds of questions you will see:
- Definitions: define NFA, DFA, acceptance by NFA, dead state, subset construction.
- Short notes: explain subset construction and the worst-case DFA state blow-up of up to 2^n states.
- Derivations/proofs: prove L(N) = L(D) by induction; show why δ_D is correct.
- Conversions: given an NFA, convert it to a DFA — show transition table and draw the DFA, indicate unreachable states.
- Diagrams: draw NFA and the DFA after subset construction; label start and accepting states.
- Application question: design an NFA for a given regular expression and convert it to a DFA.
What a full-marks answer includes:
- Precise formal definitions (5-tuples and function types).
- Correct subset-construction algorithm with δ_D formula.
- Complete transition table for reachable subsets.
- Correctly identified start and accepting subsets, and a clear diagram (or labelled state table).
- If asked, a short formal proof (induction) of equivalence.
Quick check
- Give the formal type/signature of the transition function δ in an NFA.
- In subset construction, what is the start state of the DFA (no ε-transitions)?
- If an NFA has n states, what is the worst-case number of states in the constructed DFA?
Answers: 1) δ: Q × Σ → P(Q). 2) {q0} (the singleton containing the NFA start state). 3) 2^n.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?