Sampling different kinds of acyclic automata using Markov chains (Q442144)

This paper is concerned with the random generation of (minimal) acyclic deterministic finite-state automata. Two algorithms are presented: (a) to generate acyclic automata, and (b) to generate minimal acyclic automata. Both algorithms iteratively change some transitions in an initial \(n\)-state (minimal) acyclic automaton, while keeping the same state space, acyclicity and, if applicable, minimality. The modified transitions are selected randomly. The authors prove that for both algorithms, the Markov chain describing the random amendments is ergodic and symmetric. By standard results in Markov chain theory it follows that the stationary distribution of the Markov chain is uniform.