3
$\begingroup$

I need to generate a Deterministic Finite Automata (DFA), selected from all possible DFAs that satisfy the properties below. The DFA must be selected with uniform distribution.

The DFA must have the following four properties:

- The DFA has N nodes. - Each node has 2 outgoing transitions. - Each node is reachable from every other node. - The DFA is chosen with perfectly uniform randomness from all possibilities. 

Here are three algorithms that don't work:

Algorithm #1

  1. Start with a set of N nodes called A.

  2. Choose a node from A and put it in set B.

  3. While there are nodes left in set A

    • 3.1 Choose a node x from set A

    • 3.2 Choose a node y from set B with less than two outgoing transitions.

    • 3.3 Choose a node z from set B

    • 3.4 Add a transition from y to x.

    • 3.5 Add a transition from x to z

    • 3.6 Move x to set B

  4. For each node n in B

    • 4.1 While n has less than two outgoing transitions

    • 4.2 Choose a node m in B

    • 4.3 Add a transition from n to m

  5. Choose a node to be the start node.

  6. Choose some number of nodes to be accepting nodes.

Algorithm #2

  1. Start with a directed graph with N vertices and no arcs.

  2. Generate a random permutation of the N vertices to produce a random Hamiltonian cycle, and add it to the graph.

  3. For each vertex add one outgoing arc to a randomly chosen vertex.

Algorithm #3

  1. Start with a directed graph with N vertices and no arcs.

  2. Generate a random directed cycle of some length between N and 2N and add it to the graph.

  3. For each vertex add one outgoing arc to a randomly chosen vertex.

I created algorithm #3 based off of algorithm #2, however, I don't know how to select the random directed cycle to create a uniform distribution. I don't even know if it's possible.

Any help would be greatly appreciated.

  • 0
    @JeffB: It works, but it may not be efficient. With $N=4$, there are $3^4 = 81$ possibilities if you think each node has 3 choices of a pair of different outgoing transitions, and 12 of these will not have each node reachable from every other. This will vary with $N$ and also if you I have misunderstood the rules (for example if a transition can lead back to the same place, or if the pair of transitions can lead to identical places)2011-04-03

2 Answers 2

2

Reachability is the difficult part. And also non-isomorphism. Without those it is easy: in a DFA every state has exactly one transition out (to some state) for each element of the alphabet (which is of size 2). Also, there are $n$ start states, and $2^n$ final state subsets. So for $n$ states, there are $n^{2n}\cdot n \cdot 2^n$ distinct labeled DFAs, which can be generated uniformly at random.

To get reachability, you can generate and test for reachability (using DFS), throwing out those that don't meet the reachability requirements. This will also be uniform at random (see Rejection sampling; note the section on Drawbacks).

To do this directly (without generate and test), you'd have to come up with a combinatorial description of DFAs with the reachability requirement. It doesn't seem so straightforward to me at the moment.

Non-isomorphism is doable (I think) but you'll need quite a bit of algebraic machinery using Polya counting (once (and if) if you have a combinatorial description). And for every $n$ there's quite a bit of computation to do just to create the model to then generate items from.

So my recommendation is to do the much more efficient version of generate and test (allowing possibly isomorphic DFAs).

1

In the folowing paper published there is a generalisation of the method developped by Cyril Nicaud to randomly generate with a Uniform Distribution DFAs:

http://paranthoen.thomas.free.fr/PAPERS/RandDFAToAppearInTCS.ps.gz

Note that it is also introduced in this paper that almost all DFAs are minimals. Testing a minimization algorithm with this random generator may be difficult : it is 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.

Thomas.