State Hierarchy for One-Way Finite Automata
Viliam Geffert · Journal of automata, languages and combinatorics · 2007
Quite recently, it has been shown that, for each $n$, and each $d$ between $n$ and $2^n$, there exists a regular language for which each optimal nondeterministic one-way finite state automaton (nfa) uses exactly n states, but its optimal deterministic counterpart (dfa) exactly $d$ states. This gives the complete state hierarchy for the relation between nfa's and dfa's. However, in literature, either the size of the input alphabet for these automata is very large, namely, $2^{n-1}+1$, or the argument is `non-constructive,' proving the mere existence without an explicit exhibition of the witness language. We shall give a simpler `constructive' proof for this state hierarchy, displaying explicitly the witness automata and, at the same time, reduce the input alphabet size. That is, we shall present a construction of an optimal nfa with $n$ states, and with the input alphabet size bounded by $n+2$, for which the equivalent optimal dfa uses exactly $d$ states, for each given $n$ and $d$ satisfying $n\leq d\leq 2^n$.