×

A family of NFAs which need 2\(^{n}-\alpha\) deterministic states. (English) Zbl 1022.68067

Summary: We show that for all integers \(n\geqslant 7\) and \(\alpha\), such that \(5\leqslant \alpha \leqslant 2n-2\) and satisfying some coprimality conditions, there exists a minimum \(n\)-state nondeterministic finite automaton that is equivalent to a minimum deterministic finite automaton with exactly \(2^n-\alpha\) states.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701
[2] Iwama, K.; Kambayashi, Y.; Takaki, K., Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs, Theoret. Comput. Sci., 237, 485-494 (2000) · Zbl 0939.68068
[3] G. Jirásková, Note on minimal finite automata, Proc. 26th Internat. Symp. Mathematical Foundations of Computer Science (MFCS2001), Bratislava, 2000, Lecture Notes in Computer Science, Vol. 2136, 2001, pp. 421-431.; G. Jirásková, Note on minimal finite automata, Proc. 26th Internat. Symp. Mathematical Foundations of Computer Science (MFCS2001), Bratislava, 2000, Lecture Notes in Computer Science, Vol. 2136, 2001, pp. 421-431.
[4] Lewis, H.; Papadimitriou, C., Elements of the Theory of Computation (1981), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0464.68001
[5] O.B. Lupanov, Uber den Vergleich zweier Typen endlicher Quellen, Probleme der Kybernetik, Vol. 6, Akademie-Verlag, Berlin, 1966, pp. 329-335.; O.B. Lupanov, Uber den Vergleich zweier Typen endlicher Quellen, Probleme der Kybernetik, Vol. 6, Akademie-Verlag, Berlin, 1966, pp. 329-335. · Zbl 0168.25902
[6] Moore, F., On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata, IEEE Trans. Comput., C-20, 1211-1214 (1971) · Zbl 0229.94033
[7] Rabin, M.; Scott, D., Finite automata and their decision problems, IBM J. Res. Dev., 3, 114-125 (1959) · Zbl 0158.25404
[8] Salomaa, A., Computation and Automata (1985), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0565.68046
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.