State Hierarchy for One-Way Finite Automata

Quite recently, it has been shown that, for each n, and each d between n and 2n, 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, 2n-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≤d≤2n.