Affiliations: Department of Computer Science, University of
Auckland, Private Bag 92019, Auckland, New Zealand. E-mail:
[email protected] | Department of Computer Science and Information
Technology, University of Prince Edward Island, Charlottetown, P.E.I., C1A 4P3,
Canada. E-mail: [email protected] | Department of Probability Theory Statistics and
Operational Research, Faculty of Mathematics and Informatics, Str. Academiei
14, Bucharest, Romania. E-mail: [email protected]
Abstract: 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.
