×

Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs. (English) Zbl 0939.68068

Summary: It is shown that if \(\alpha\) is an integer which can be expressed as \(2^{k}\) or \(2^{k}+1\) for some integer \(0< k< n/2-2\), then there exist nondeterministic finite automata with n states whose equivalent deterministic finite automata need exactly \(2^{n}-\alpha\) states.

MSC:

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

References:

[1] A. Ambainis, The complexity of probabilistic versus deterministic finite automata, Proc. 7th ISAAC, Lecture Notes in Computer Science, Vol. 1178, Springer, Berlin, 1996, pp. 231-238.; A. Ambainis, The complexity of probabilistic versus deterministic finite automata, Proc. 7th ISAAC, Lecture Notes in Computer Science, Vol. 1178, Springer, Berlin, 1996, pp. 231-238. · Zbl 1036.68510
[2] P. Berman, A. Lingas, On complexity of regular languages in terms of finite automata, ICS PAS Report 304, Warszawa, 1979.; P. Berman, A. Lingas, On complexity of regular languages in terms of finite automata, ICS PAS Report 304, Warszawa, 1979. · Zbl 0364.68057
[3] Harrison, M., Introduction to Formal Language Theory (1978), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0411.68058
[4] Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701
[5] Lewis, H.; Papdimitoriou, C., Elements of the Theory of Computation (1981), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ
[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] Nozaki, A., Equivalence problem of non-deterministic finite automata, J. Comput. System Sci., 18, 8-17 (1979) · Zbl 0401.68028
[8] Rabin, M.; Scott, D., Finite automata and their decision problems, IBM J. Res. Dev., 3, 114-125 (1959) · Zbl 0158.25404
[9] 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.