Overview
DFA construction, often called subset construction, treats each reachable set of NFA states as one deterministic state. Transitions are computed by moving on a symbol and taking closure as required.
CoreSource checked
DFA Construction
Builds a deterministic finite automaton by grouping NFA state sets into DFA states.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Parsing
- Difficulty
- Intermediate
- Family
- Automata Construction
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 6
- Code example
- Ready
- Visualization
- Ready
Core Concepts
deterministic statesubset constructiontransition tableregular language
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(states)
Average
O(2^n)
Worst
O(2^n)
Space
O(2^n)
When to Use
- Use when deterministic scanning speed is more important than possible state blowup.
- Use when the input language is regular and represented as an NFA.
When Not to Use
- Avoid when the subset explosion would make the DFA too large.
- Avoid for context-free grammar parsing; the method is for regular languages.
What It Does
- Starts from an NFA start-state set
- Creates DFA states from reachable NFA-state subsets
- Adds deterministic transitions for each input symbol
Use Cases
- Regular-expression engines
- Lexer construction
- Converting nondeterministic automata into deterministic recognizers
Inputs
- Tokens or grammar
- Parser state
Outputs
- Parse tree
- Automaton
- Grammar table or parse result
Key Formulas (1)
Subset transition
DFAnext(S, char) = εclosure(move(S, char))
DFA_next(S, char) = epsilon_closure(move(S, char))Builds a deterministic transition from a set of NFA states.
Pseudocode
- 1.Compute the epsilon-closure of the NFA start state
- 2.Create the first DFA state from that set
- 3.While an unprocessed DFA state remains
- 4.For each input symbol, move every NFA state in the set on that symbol
- 5.Take epsilon-closure of the result and create or reuse the target DFA state
- 6.Mark DFA states accepting when their NFA-state set contains an accepting state
Canonical Example
- Input
- an NFA for tokens 'a' or 'ab'
- Output
- DFA states represented by reachable NFA-state sets
- Explanation
- Each DFA state summarizes all NFA states that could be active after a prefix.
Implementation Notes
- Represent state sets in a canonical sorted or bitset form.
- Use a work queue of unprocessed DFA state sets.
- Test with an NFA that has epsilon transitions and multiple accepting states.
Common Pitfalls
- Forgetting epsilon-closure creates missing transitions.
- Not marking accepting DFA states when any member NFA state accepts.
- Failing to canonicalize state sets creates duplicate DFA states.
Interactive Mechanism Walkthrough
Sequence Window & Automaton AlignmentShow grammar items, parser states, and consumed input as parsing progresses.
Input:ABABABCABAB
Window:ABAB
Step 1 of 6: Compute the epsilon-closure of the NFA start state
parsing-mechanismNotes
Subset construction trades nondeterminism for potentially many deterministic states.
Sources (1)
What each reference supports for this entry.
Introduction to Automata Theory, Languages, and Computation
BookAutomata textbook support for DFA Construction's state-machine construction, language recognition, and correctness model.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Used byRegular Expression Matching
Pattern Matching · Core
Regular-expression matching can compile patterns to finite automata before scanning text.
Compare with thisUsesThompson's Construction
Parsing · Core
A regex engine may build an NFA with Thompson's construction before DFA construction.
Compare with thisRelationships
View full relationship pageA regex engine may build an NFA with Thompson's construction before DFA construction.
Conceptual neighborNFA Simulation
NFA simulation keeps sets of active states at run time instead of materializing the full DFA.
Related Algorithms
Tags
ParsingAutomatonRegular ExpressionTokenization