Conjecture that any synchronizing automaton with n states has a reset word of length (n - 1)(2) was made by. Cerny in 1964. Notwithstanding the numerous attempts made by various researchers this conjecture hasn't been definitively proven yet. In this paper we study a random automaton that is sampled uniformly at random from the set of all automata with n states and m(n) letters. We show that for m(n) > 18 ln n any random automaton is synchronizing with high probability. For m(n) > n(beta), beta > 1/2 we also show that any random automaton with high probability satisfies the. Cerny conjecture.
Discrete Mathematics & Theoretical Computer Science
