Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
To assign positive uniform probabilities would require a finite set of possibilities. Perhaps you have in mind a notion of DFA's equivalent up to relabelling of nodes, or perhaps you have in mind a fixed set of N labelled nodes. No doubt the uniform probabilities will depend on which approach is taken. –  hardmath Apr 3 '11 at 19:30
    
The DFA must have N nodes. It cannot have less than N nodes. Since all DFAs have N nodes, and the number of permutations on N nodes is always N!, the number of isomorphic graphs from relabeling will be the same for all DFAs. That is, it doesn't matter whether isomorphic DFAs are considered or not. –  user9049 Apr 3 '11 at 19:33
    
You could always choose one with N nodes and 2 outgoing transitions, then check whether each node is reachable from every other, and if so stop. If not then try again. –  Henry Apr 3 '11 at 20:34
    
@Henry: Are you sure this will this give me a perfectly uniform distribution? –  user9049 Apr 3 '11 at 20:37
    
@Jeff B.: You have overlooked the possibility some orbits may be less than N! because a permutation of labels may (for example) yield the same DFA you start with. –  hardmath Apr 3 '11 at 21:06
show 2 more comments

2 Answers 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).

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.