9
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ There's no natural distribution of random DFAs, so it's up to you. What do you want to accomplish? $\endgroup$
    – Yuval Filmus
    Jun 28, 2013 at 5:29
  • $\begingroup$ I am generating random DFAs to test a DFA reduction algorithm on them. $\endgroup$
    – Duncan
    Jun 28, 2013 at 5:32
  • $\begingroup$ Perhaps you want to start from a small set of minimal DFAs and blow them up? That way you know that the minimization actually arrives at the right result. $\endgroup$
    – adrianN
    Jun 28, 2013 at 9:30
  • $\begingroup$ wondering, are you testing a nonoptimal reduction algorithm or is it finding the unique minimal optimum DFA? $\endgroup$
    – vzn
    Jun 28, 2013 at 17:25
  • 2
    $\begingroup$ If you're generating data structures for testing, unbiased isn't important. What's important is to have a good chance of triggering interesting behaviors. To take an analogy, when you test a geometric algorithm, you need to ensure that some of your tests will have three points aligned and other things that would never occur in a random distribution. $\endgroup$
    – Gilles 'SO- stop being evil'
    Jun 29, 2013 at 8:43

4 Answers 4

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ What does "canonical string representations" mean? $\endgroup$
    – Duncan
    Jun 29, 2013 at 3:01
  • $\begingroup$ @drowse The canonical order is defined over the set of states by traversing the automaton in a breadth-first way choosing at each node the outgoing using the (total) order of $\Sigma$. Check out the references in the paper. $\endgroup$
    – Juho
    Jun 29, 2013 at 16:54
4
$\begingroup$

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.

Improve this answer
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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].

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ FYI: cs.stackexchange.com/review/suggested-edits/6609 $\endgroup$
    – Gilles 'SO- stop being evil'
    Aug 18, 2013 at 8:17
  • $\begingroup$ re the edit, another way to see DFAs is as a set of triples defining edges $(v_1,b,v_2)$ where $v_1$ is vertex 1, $v_2$ vertex 2, and $b$ is the transition symbol and any subset of these can be chosen to determine a DFA. $\endgroup$
    – vzn
    Sep 15, 2013 at 17:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.