DFA minimization

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

DFA minimization is the process of turning a given deterministic finite automaton (DFA) into the smallest possible DFA that recognizes the same language. For every regular language, there is a smallest DFA, and it is unique up to naming of the states.

How minimization works in simple terms
- First remove any states that can never be reached from the start state. These unreachable states don’t affect the language.
- Then merge states that behave the same way on every possible input sequence (these are called indistinguishable states). Different algorithms do this merging in different ways.

Two common methods to merge indistinguishable states

1) Hopcroft’s algorithm (partition refinement)
- Start by grouping states into two blocks: accepting and non-accepting.
- Repeatedly refine these blocks by splitting them based on where transitions on each input symbol would lead.
- This refinement keeps splitting blocks until no more splits are possible.
- The result partitions states into equivalence classes. Each class becomes a single state in the minimal DFA; transitions go between these classes the same way they would between the original states. The initial and accepting blocks determine the start and final states.
- Why it’s fast: it splits blocks in a way that, for every transition, the relevant parts shrink quickly. Running time is very efficient (often near n log n for n states and s input symbols).

2) Moore’s algorithm
- Also starts with a partition into accepting vs non-accepting states.
- Repeatedly refines the partition by checking, for every input symbol, how states move and which ones end up in the same block.
- Stop when a full pass doesn’t change anything.
- Worst-case time is higher (about n^2 times the number of symbols), but it’s simple to understand and implement.

Building the minimal DFA
- After the refinement, each block of states becomes one state in the minimized DFA.
- A block’s transitions on each input symbol go to the block that contains the original destination state.
- The start state is the block containing the original start state, and a block is accepting if any state in it was accepting.

Brzozowski’s algorithm (a different approach)
- Reverse the DFA’s language by reversing transitions and swapping start/final states to get an NFA, determinize it, reverse again, and determinize once more.
- The result is the minimal DFA for the original language.
- This method is simple but can be very slow in the worst case (exponential time in the number of states).

Notes on NFAs
- The partitioning methods above work for DFAs. Minimizing NFAs (nondeterministic finite automata) is much harder, with no known polynomial-time algorithm in general unless a major complexity breakthrough is found. There are practical methods to simplify NFAs, but not guaranteed minimal ones.

Key idea
- There is a unique smallest DFA for every regular language, and minimization is all about removing unreachable states and merging states that cannot be distinguished by any input sequence.