[Solved]: What is a good algorithm for generating random DFAs?

Problem Detail: 

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?

Asked By : Duncan

Answered By : Juho

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12943