Deterministic blow-ups of minimal nondeterministic finite automata over a fixed alphabet
We show that for all integers n and a such that n <= alpha a <= 2(n), there exists a minimal nondeterministic finite automaton of n states with a four-letter input alphabet whose equivalent minimal deterministic finite automaton has exactly a states. It follows that in the case of a four-letter alphabet, there are no "magic numbers", i.e., the holes in the hierarchy. This improves a similar result obtained by Geffert for a growing alphabet of size n + 2.
deterministic and nondeterministic finite automata minimal automata