I need to create deterministic finite state machines (DFAs) selected from all possible DFAs that satisfy the properties below. DFA should be chosen with a uniform distribution.
DFA must have the following four properties:
- DFA has N nodes.
- Each node has 2 outgoing transitions.
- Each node is accessible from all other nodes.
- DFA is chosen with absolutely uniform randomness from all possibilities.
I do not consider labeling nodes or transitions. If two DFAs have the same unlabeled directed graph, they are considered the same.
Here are three algorithms that do not work:
Algorithm # 1
- Start with a set of N nodes called A.
- Select a node from A and put it in a set B.
As long as 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 every 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
Algorithm # 2
- Start with a directed graph with N vertices and no arcs.
- Create a random permutation of N vertices to create a random Hamiltonian cycle and add it to the graph.
- For each vertex, add one outgoing arc to a randomly selected vertex.
Algorithm # 3
- Start with a directed graph with N vertices and no arcs.
- Create 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 selected vertex.
I created Algorithm No. 3 based on Algorithm No. 2, however I don’t know how to choose a random directed cycle to create a uniform distribution. I don’t even know if this is possible.
Any help would be greatly appreciated.
source share