  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 digraph). In 1973 Grusho first proved that with high
probability (whp) in a random $k$-out digraph there is a strongly connected
component (SCC) of linear size that is reachable from all vertices, i.e., a
giant. He also proved that the size of the giant follows a central limit law.
We show that whp the part outside the giant contains at most a few short cycles
and mostly consists of overlapping tree-like structures. Thus the directed
acyclic graph (DAG) of a random $k$-out digraph is almost the same as the
digraph with the giant contracted into one vertex. These findings lead to a
new, concise and self-contained proof of Grusho's theorem. This work also
contains some other results including the structure outside the giant, the
phase transition phenomenon in strong connectivity, the typical distance, and
an extension to simple digraphs.
