What is a good algorithm for generating random DFAs?

Question

I am generating random DFAs to test a DFA reduction algorithm on them.

The algorithm that I'm using right now is as follows: for each state $q$, for each symbol in the alphabet $c$, add $\delta (q, c)$ to some random state. Each state has the same probability of becoming a final state.

Is this a good method of generating unbiased DFAs? Also, this algorithm doesn't generate a trim DFA (a DFA with no obsolete states) so I'm wondering if there is a better way of generating random DFAs that can somehow ensure that it is trim?

Answer 1

Check out [1] and the discussion in Section 4, Random Automata Generation. The paper benchmarks different DFA minimization algorithms. A uniform random generator is used that produces canonical string representations of complete DFAs with $n$ states and $k$ symbols. They also discuss other methods.

---

[1] Almeida, M., Moreira, N., & Reis, R. (2007). On the performance of automata minimization algorithms. Logic and Theory of Algorithms, 3.

Answer 2

You should look at Cyril Nicaud's homepage. In particular, the following references are relevant to your question:

F. Bassino, J. David and C. Nicaud, Enumeration and random generation of possibly incomplete deterministic automata, Pure Mathematics and Applications 19 (2-3) (2009) 1-16.

F. Bassino and C. Nicaud. Enumeration and Random Generation of Accessible Automata. Theor. Comp. Sc.. 381 (2007) 86-104.

Answer 3

There are algorithms to randomly generate DFAs up to a permutation http://paranthoen.thomas.free.fr/PAPERS/RandDFAToAppearInTCS.ps.gz.

But, it is also mentionned in the above paper that almost all DFAs are already minimal. Non minimal DFAs are like prime numbers ... there are just few of them. And if you use this algorithm to test minimization algorithm it will be like if you were testing an algorithm on prime number with a simple random number generator. In order to have more non minimal DFAs, you may alter the algorithm by adding a sink state, and redirect an important percentage of the transitions to this sink state.

But from my point of view, if you want to test the speediness of your implementation, check it against what you want to use it for: with random word sets or random REGEX, create a NFA or a DFA, and then minimize the resulting DFA.

Answer 4

one natural strategy is to regard the DFA as a graph and then there are many "natural" and highly studied random distributions of graphs, the simplest is probably Erdos-Renyi. in that case you treat all states of the DFA as nodes of the graph and some fixed percent of all possible edges (DFA transitions) are chosen. more sophisticated distributions that are studied much in the more recent era are small world graphs. for the strategy you mention in your question you are apparently choosing the special case $p=1/n$ where $n$ is the number of nodes in the graph. however your strategy, nor Erdos-Renyi, does not guarantee that all the states in the DFA are connected [a natural constraint to add].