CD Notes
Detailed guide to Nondeterministic Finite Automata covering formal definition, epsilon transitions, NFA to DFA conversion using subset construction, and Thompson construction for regex.
Introduction
A Nondeterministic Finite Automaton (NFA) is a finite automaton where the transition function allows multiple possible next states for a given (state, input) pair. Unlike DFAs, NFAs can "guess" the correct path through non-determinism — they accept a string if there exists at least one accepting computation path.
NFAs are crucial in compiler design because Thompson's construction converts regular expressions directly to NFAs, which are then systematically converted to DFAs for efficient token recognition.
Formal Definition
An NFA is a 5-tuple: M = (Q, Σ, δ, q₀, F) where:
- Q = finite set of states
- Σ = finite input alphabet
- δ = transition function, δ: Q × (Σ ∪ {ε}) → P(Q) (power set of Q)
- q₀ = initial state, q₀ ∈ Q
- F = set of final/accepting states, F ⊆ Q
The key distinction: δ returns a SET of states, not a single state.
NFA State Diagram Example
Transition table
| State | a | b |
|---|---|---|
| →q0 | {q0,q1} | {q0} |
| q1 | ∅ | {q2} |
| *q2 | ∅ | ∅ |
Simplified (same NFA)
How NFA Accepts Strings
An NFA accepts string w if there EXISTS at least one path from start state to a final state on input w.
| a | q0 q1 |
| a | q0 q1 (dead, no 'a' transition) |
| b | q0 q2 ← ACCEPTING STATE REACHED! |
| b | q0 |
| a | q0 q1 (q1 is not final, q0 is not final) |
| No final state reached | "ba" is REJECTED. |
Epsilon (ε) Transitions
ε-transitions allow state changes without consuming any input character:
ε-Closure Algorithm
| function ε-closure(T) | // T is a set of states |
| ε-transitions: q0 | q1, q1→q2, q0→q3 |
| pop q0 | δ(q0,ε) = {q1, q3} |
| add q1, q3 | result = {q0,q1,q3}, stack = [q1,q3] |
| pop q3: δ(q3,ε) = {} | nothing |
| pop q1 | δ(q1,ε) = {q2} |
| add q2 | result = {q0,q1,q2,q3}, stack = [] |
move() Function
move(T, a) = set of states reachable from states in T on input symbol a
= ∪{δ(t, a) | t ∈ T}
Example:
δ(q0, a) = {q1, q2}
δ(q1, a) = {q3}
δ(q2, a) = {}
move({q0, q1, q2}, a) = δ(q0,a) ∪ δ(q1,a) ∪ δ(q2,a)
= {q1,q2} ∪ {q3} ∪ {}
= {q1, q2, q3}
NFA to DFA Conversion (Subset Construction)
This is the most important algorithm connecting NFAs to practical lexer implementation.
DFA Transition Table
| State | a | b |
|---|---|---|
| →A | B | C |
| B | B | D |
| C | B | C |
| D | B | E |
| *E | B | C |
Mark S
Detailed Example
State transitions
Thompson's Construction
Thompson's construction converts regular expressions to ε-NFAs systematically:
| Rule 1 | Single character 'a' |
| Rule 2 | Concatenation r₁r₂ |
| Rule 3 | Union r₁|r₂ |
| ε── | [NFA₁]──ε |
| ε── | [NFA₂]──ε |
| Rule 4 | Kleene Star r₁* |
| Example | Build NFA for a(b|c)* |
| Step 1: NFA for 'a': [1]──a── | [2] |
| Step 2: NFA for 'b': [3]──b── | [4] |
| Step 3: NFA for 'c': [5]──c── | [6] |
| Step 4 | NFA for b|c: |
| [7]──ε── | [3]──b──→[4]──ε──→[8] |
| └──ε── | [5]──c──→[6]──ε──→[8] |
| Step 5 | NFA for (b|c)*: |
| [9]──ε── | [7]──...──[8]──ε──→[10] |
| └─────────────ε───────────── | [10] |
| [8]──ε── | [7] (loop back) |
| Step 6 | Concatenate a with (b|c)*: |
Properties of NFAs
| Property | Details |
|---|---|
| Acceptance | ∃ path to final state |
| Equivalent to DFA? | Yes, same power |
| May have ε-transitions? | Yes |
| Transition returns | Set of states (possibly ∅) |
| Dead state needed? | No, empty set = rejection |
| More compact than DFA? | Usually yes |
| Direct implementation? | Inefficient (backtrack) |
NFA Simulation Algorithm
| Algorithm | Simulate NFA on input string w |
| 3. If current_states ∩ F ≠ ∅ | ACCEPT |
| Else | REJECT |
| Time complexity | O(n × m²) where n = |w|, m = |Q| |
NFA for Pattern Matching
NFAs are naturally suited for pattern matching because non-determinism handles "trying all possibilities":
Comparison: NFA vs DFA for Compiler Use
Interview Questions
- Q: If an NFA has n states, what is the maximum number of states in the equivalent DFA?
A: 2ⁿ states (each DFA state is a subset of NFA states). However, most practical conversions produce far fewer reachable states. The worst case is actually achieved by specific NFAs like "the nth symbol from the end is a."
- Q: Can an NFA accept a string through a path that passes through a final state but does not end there?
A: No. The NFA accepts only if, after consuming the ENTIRE input string, the current set of possible states includes at least one final state. Passing through a final state mid-way does not constitute acceptance.
- Q: Why are NFAs preferred over DFAs for representing regular expressions initially?
A: Thompson's construction produces an NFA with at most 2n states for a regex of length n, with simple structure (each state has at most 2 outgoing transitions). Building a DFA directly from a regex would require handling exponential blowup during construction.
- Q: How does the compiler handle the case where multiple NFA final states are reached simultaneously?
A: In a multi-pattern scanner, each final state is tagged with a token type. If multiple final states are reached, priority rules determine which token is emitted (e.g., keywords have higher priority than identifiers). The longest match rule also applies.
- Q: Explain the relationship between non-determinism in NFAs and backtracking in parsing.
A: NFA non-determinism means multiple paths are explored simultaneously (conceptually). In parsing, this translates to trying different grammar rules. Subset construction eliminates non-determinism for scanning; for parsing, techniques like LL(k) lookahead or LR item sets serve a similar role in making deterministic choices.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Nondeterministic Finite Automata (NFA) in Compiler Design.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.
Search Terms
compiler-design, compiler design, compiler, design, automata, and, formal, languages
Related Compiler Design Topics