DFA Minimization
The process of reducing a DFA to an equivalent automaton with the minimum number of states for the same regular language.
DFA minimization is more than deleting unreachable states. The core task is to merge states that cannot be distinguished by any future input sequence.
Partition Refinement
Hopcroft-style minimization begins with accepting and non-accepting partitions and refines them whenever transition behavior proves two groups distinguishable. With appropriate data structures, the classic bound is O(|Sigma| * n log n).
This matters in lexer generation, protocol parsers, and model-based tooling because fewer states can reduce both table size and transition complexity.
Boundary
NFA minimization is a different problem. Determinization may cause state explosion before minimization, so a small final DFA does not imply a cheap conversion pipeline.
Source
- https://arxiv.org/abs/1010.5318