zbMATH — the first resource for mathematics

State hierarchy for one-way finite automata. (English) Zbl 1149.68049
Summary: 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 the 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 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 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\).
68Q45 Formal languages and automata
Full Text: DOI