The graph structure of a deterministic automaton chosen at random
Xing Shi Cai, Luc Devroye · Random Structures and Algorithms · 2016
Abstract Ann‐state deterministic finite automaton over ak‐letter alphabet can be seen as a digraph withnvertices which all haveklabeled out‐arcs. Grusho (Publ Math Inst Hungarian Acad Sci 5 (1960), 17–61). proved that whp in a randomk‐out digraph there is a strongly connected component of linear size, i.e., a giant, and derived a central limit theorem. We show that whp the part outside the giant contains at most a few short cycles and mostly consists of tree‐like structures, and present a new proof of Grusho's theorem. Among other things, we pinpoint the phase transition for strong connectivity. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 51, 428–458, 2017