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
    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.2011-04-03
  • 0
    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.2011-04-03
  • 0
    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.2011-04-03
  • 0
    @Henry: Are you sure this will this give me a perfectly uniform distribution?2011-04-03
  • 0
    @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.2011-04-03
  • 0
    If it yields the same DFA I start with then I would not include it in my set. In other words, if the underlying directed graphs of the DFAs are isomorphic, then they count as 1 element in the set.2011-04-03
  • 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