×

Magic numbers in the state hierarchy of finite automata. (English) Zbl 1132.68444

Královič, Rastislav (ed.) et al., Mathematical foundations of computer science 2006. 31st international symposium, MFCS 2006, Stará Lesná, Slovakia, August 28–September 1, 2006. Proceedings. Berlin: Springer (ISBN 3-540-37791-3/pbk). Lecture Notes in Computer Science 4162, 412-423 (2006).
Summary: A number \(d\) is magic for \(n\), if there is no regular language for which an optimal nondeterministic finite state automaton (nfa) uses exactly \(n\) states, but for which the optimal deterministic finite state automaton (dfa) uses exactly \(d\) states. We show that, in the case of unary regular languages, the state hierarchy of dfa’s, for the family of languages accepted by \(n\)-state nfa’s, is not contiguous. There are some “holes” in the hierarchy, i.e., magic numbers in between values that are not magic. This solves, for automata with a single letter input alphabet, an open problem of existence of magic numbers [K. Iwama, Y. Kambayashi and K. Takaki, “Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs”, Theor. Comput. Sci. 237, No. 1–2, 485–494 (2000; Zbl 0939.68068)].
As an additional bonus, we get a universal lower bound for the conversion of unary \(d\)-state dfa’s into equivalent nfa’s: nondeterminism does not reduce the number of states below \(\log^{2} d\), not even in the best case.
For the entire collection see [Zbl 1114.68008].

MSC:

68Q45 Formal languages and automata

Citations:

Zbl 0939.68068
PDFBibTeX XMLCite
Full Text: DOI