The graph structure of a deterministic automaton chosen at random: full version

Xing Shi Cai, Luc Devroye

A deterministic finite automaton (DFA) of $n$ states over a $k$-letter alphabet can be seen as a digraph with $n$ vertices which all have exactly $k$ labeled out-arcs ($k$-out digr…