Distribution of the number of accessible states in a random deterministic automaton

Arnaud Carayol & Cyril Nicaud
We study the distribution of the number of accessible states in deterministic and complete automata with n states over a k-letters alphabet. We show that as n tends to infinity and for a fixed alphabet size, the distribution converges in law toward a Gaussian centered around vk n and of standard deviation equivalent to sk n^(1/2), for some explicit constants vk and sk. Using this characterization, we give a simple algorithm for random uniform generation...