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
Start with a set of N nodes called A.
Choose a node from A and put it in set B.
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
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
Choose a node to be the start node.
Choose some number of nodes to be accepting nodes.
Algorithm #2
Start with a directed graph with N vertices and no arcs.
Generate a random permutation of the N vertices to produce a random Hamiltonian cycle, and add it to the graph.
For each vertex add one outgoing arc to a randomly chosen vertex.
Algorithm #3
Start with a directed graph with N vertices and no arcs.
Generate a random directed cycle of some length between N and 2N and add it to the graph.
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.