HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

What is a good algorithm for generating random DFAs?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
randomwhatalgorithmgeneratingdfasforgood

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#12943, answer score: 6

Revisions (0)

No revisions yet.