Automata Recognizing No Words: A Statistical Approach
Automata Recognizing No Words: A Statistical Approach
复制标题
DOI：
--
复制
发表时间：
2006-10
期刊：
影响因子：
--
通讯作者：
Cristian S. Calude;C. Câmpeanu;M. Dumitrescu
中科院分区：
文献类型：
--
作者：
Cristian S. Calude;C. Câmpeanu;M. Dumitrescu
随机给定的(非)确定性有限自动机不识别单词的可能性有多大？快速反思似乎表明，没有太多的有限自动机不接受单词；但是，这一直觉能得到证实吗？在这篇文章中，我们提供了一种统计方法，它允许我们得出结论：对于具有足够多状态的自动机，给定的(非)确定的有限自动机不识别任何单词的概率接近于零。更准确地说，我们将以高精度(即，精度高于99%，置信度为0.9973)证明，对于确定性和非确定性有限自动机：a)当状态数和字母表中的字母数趋于无穷大时，自动机不识别任何单词的概率趋于零，b)如果状态数是固定的且相当小，则即使自动机的字母表的字母数趋于无穷，概率也是严格正的。结果a)是通过统计分析得到的；b)我们使用组合和统计分析。目前的分析表明，对于所有实际目的，当状态数和字母表中的字母数无限增长时，自动机不识别任何单词的比例趋于零。从理论的角度来看，这一结果可以激发人们寻找“确定性”的动机，也就是用概率术语证明这里所确立的事实。在最后一节中，我们批判性地讨论了本文的结果和所使用的方法。
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.