Minimization of a deterministic automaton

Back to Automaton algorithms

A minimal automaton for a language is a deterministic finite-state automaton which has the minimum number of states needed for recognizing the language. Given a deterministic automaton A, minimization is the problem of finding a minimal automaton for the language generated by A.

Algorithm

The implemented minimization algorithm (see [1]) has the following properties. It takes

• time `O(n + m log(n))`, and
• space `O(n + m)`,

where `m` is the number of transitions, and `n` is the number states. This comes with the standard caveat of using hash-tables: this behaviour can not be guaranteed in the worst-case, although differing behaviour is highly improbable. For comparison, the classical Hopcroft’s minimization algorithm takes time `O(k n log(n))`, where `k` is the number of symbols.

References

[1] “Fast brief practical DFA minimization”, Antti Valmari, Information Processing Letters, Volume 112, Issue 6, 2012, pp. 213-217.

Remark 1.7.5 - Page generated 16.06.2017 01:37.