StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POHow can I generate a random DFA with uniform distribution?
text
Body
copied!<p>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.</p> <p>The DFA must have the following four properties:</p> <ul> <li>The DFA has N nodes.</li> <li>Each node has 2 outgoing transitions.</li> <li>Each node is reachable from every other node.</li> <li>The DFA is chosen with perfectly uniform randomness from all possibilities.</li> </ul> <p>I am not considering labeling of nodes or transitions. If two DFAs have the same unlabeled directed graph they are considered the same.</p> <p>Here are three algorithms that don't work:</p> <p>Algorithm #1</p> <ol> <li>Start with a set of N nodes called A.</li> <li>Choose a node from A and put it in set B.</li> <li><p>While there are nodes left in set A</p> <pre><code> - 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 </code></pre></li> <li><p>For each node n in B</p> <pre><code> - 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 </code></pre></li> </ol> <p>Algorithm #2</p> <ol> <li>Start with a directed graph with N vertices and no arcs.</li> <li>Generate a random permutation of the N vertices to produce a random Hamiltonian cycle, and add it to the graph.</li> <li>For each vertex add one outgoing arc to a randomly chosen vertex.</li> </ol> <p>Algorithm #3</p> <ol> <li>Start with a directed graph with N vertices and no arcs.</li> <li>Generate a random directed cycle of some length between N and 2N and add it to the graph.</li> <li>For each vertex add one outgoing arc to a randomly chosen vertex.</li> </ol> <p>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.</p> <p>Any help would be greatly appreciated.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload