Random Deterministic Automata

Question

I am familiar with the term of random graphs, such as $G(n,p)$- a distribution over simple undirected graphs with $n$ vertices, where each edge appears in a graph w.p. $p$. That is, each graph $G=(V,E)$, gets a probability of $p^{|E|}\cdot (1-p)^{{{{|V|}\choose{2}}} - |E|}$. In particular, $G(n, \frac{1}{2})$ is the uniform distribution over simple undirected graphs of size $n$.

Now, given a finite alphabet $\Sigma$ and a natural number $n$. Do we have a random process that generates a deterministic automaton $A$ with:

• $A$ has $n$ reachable states.
• $A$ is defined over $\Sigma$.
• $A$ has the same probability as any other deterministic automaton of size $n$ over $\Sigma$.

In words, do we have a way to generate a uniform distribution $D(\Sigma, n,\frac{1}{2})$ over deterministic automata?

I would be happy if you can direct me to a relevant reference.

Answer 1

The question is a bit ill-posed, since you did not specify that equivalent automata should be counted as a single object. Without that restriction (or the reachability one), the set of all $n$-state DFAs over a binary alphabet and with starting state $s=1$ has exactly $n^{2n}2^n$ elements, and it is trivial to sample from this set uniformly, as indicated in the link in my comment, https://dl.acm.org/citation.cfm?id=3064434

Now the linked paper gives sharp bounds on the expected size of the minimal equivalent DFA, when the original one is drawn from the naive uniform distribution. For binary alphabets, this quantity is concentrated about $0.7968n$. That suggests that if you naively sample DFAs on $n/0.7968$ states and then minimize them, you'll get automata with roughly $n$ reachable states. Of course, no claim is being made about this sampling procedure being uniform. See, however, references in the linked paper -- especially https://dl.acm.org/citation.cfm?id=782472 and http://www.sciencedirect.com/science/article/pii/S0304397507002861?via%3Dihub -- the latter seems most relevant to your question.