Automata Recognizing No Words : A Statistical Approach

• Autorzy: Calude C.S. , Campeanu C. , Dumitrescu M.
• Języki publikacji: EN

Abstrakty

EN

How likely is that a randomly given (non-) deterministic finite automaton recognizes no word? A quick reflection seems to indicate that not too many finite automata accept no word; but, can this intuition be confirmed? In this paper we offer a statistical approach which allows us to conclude that for automata, with a large enough number of states, the probability that a given (non-) deterministic finite automaton recognizes no word is close to zero. More precisely, we will show, with a high degree of accuracy (i.e., with precision higher than 99% and level of confidence 0.9973), that for both deterministic and non-deterministic finite automata: a) the probability that an automaton recognizes no word tends to zero when the number of states and the number of letters in the alphabet tend to infinity, b) if the number of states is fixed and rather small, then even if the number of letters of the alphabet of the automaton tends to infinity, the probability is strictly positive. The result a) is obtained via a statistical analysis; for b) we use a combinatorial and statistical analysis. The present analysis shows that for all practical purposes the fraction of automata recognizing no words tends to zero when the number of states and the number of letters in the alphabet grow indefinitely. From a theoretical point of view, the result can motivate the search for ``certitude'', that is, a proof of the fact established here in probabilistic terms. In the last section we critically discuss the result and the method used in this paper.

Słowa kluczowe

EN

finite automata; emptiness problem; statistical analysis; sampling method

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 73, nr 1-2
• Strony: 1--18
• Opis fizyczny: tab., bibliogr. 12 poz.

Twórcy

autor

Calude C.S.

autor

Campeanu C.

autor

Dumitrescu M.

• Department of Computer Science, The University of Auckland, Private Bag 92019, Auckland, New Zealand,

Bibliografia

• [1] J.M. Borwein, D. Bailey: Mathematics by Experiment: Plausible Reasoning in the 21st Century. A.K. Peters, Natick, MA, 2003.
• [2] J.M. Borwein, D. Bailey, R. Girgensohn: Experimentation in Mathematics: Computational Paths to Discovery. A.K. Peters, Natick, MA, 2004.
• [3] C.S. Calude, E. Calude, M.J. Dinneen: What is the value of Taxicab6? J. UCS, 9, 10 (2003), 1196-1203.
• [4] C.S. Calude, E. Calude, T. Chiu, M. Dumitrescu, R. Nicolescu: Testing computational complementarity for Mermin automata. J. Multi Valued Logic, 6 (2001), 47-65.
• [5] C.S. Calude, S.Marcus: Mathematical proofs at a crossroad? In Theory Is Forever (J. Karhumäki, H.Maurer, G. P˘aun, G. Rozenberg, eds.), LNCS 3113, Springer, Berlin, 2004, 15-28.
• [6] W.G. Cochran: Sampling Techniques, 3rd edition. Wiley, New York, 1977.
• [7] M. Domaratzki, D. Kisman, J. Shallit: On the number of distinct languages accepted by finite automata with n states. J. Automat. Lang. Comb., 7 (2002), 469-486.
• [8] M. Dumitrescu: Statistical Surveys and Applications. Editura Tehnic˘a, Bucharest, 2000 (in Romanian).
• [9] P.J. Green, B.W. Silverman: Non-parametric Regression and Generalized Linear Models. Chapman & Hall, London, 1994.
• [10] D. Kozen: Automata and Computability. Springer, New York, 1997.
• [11] A. Salomaa: Computation and Automata. Cambridge University Press, Cambridge, 1985.
• [12] S. Yu: Regular languages. In Handbook of Formal Languages, Vol. 1 (G. Rozenberg, A. Salomaa, eds.). Springer, Berlin, 1997, 41-110.