STATE HIERARCHY FOR ONE-WAY FINITE AUTOMATA

摘要

Quite recently, it has been shown that, for each n, and each d between n and 2{sup}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{sup}(n-1)+l, 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 ≤ 2{sup}n.