algorithm - 如何生成具有均匀分布的随机 DFA？

Question

我需要生成一个确定性有限自动机 (DFA)，它是从满足以下属性的所有可能的 DFA 中选出的。必须选择均匀分布的 DFA。

DFA 必须具有以下四个属性:

• DFA 有 N 个节点。
• 每个节点都有 2 个输出转换。
• 每个节点都可以从其他所有节点访问。
• DFA 是从所有可能性中完全均匀随机选择的。

我不考虑标记节点或转换。如果两个 DFA 具有相同的未标记有向图，则它们被认为是相同的。

以下是三种不起作用的算法:

算法 #1

1. 从一组称为 A 的 N 个节点开始。
2. 从A中选择一个节点放入集合B。

3. 当集合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. 对于B中的每个节点n

     -  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
   

算法 #2

1. 从一个有 N 个顶点且没有弧的有向图开始。
2. 生成 N 个顶点的随机排列以生成随机哈密顿循环，并将其添加到图中。
3. 对于每个顶点，将一个出向弧添加到随机选择的顶点。

算法#3

1. 从一个有 N 个顶点且没有弧的有向图开始。
2. 生成一个长度介于 N 和 2N 之间的随机有向循环，并将其添加到图中。
3. 对于每个顶点，将一个出向弧添加到随机选择的顶点。

我基于算法 #2 创建了算法 #3，但是，我不知道如何选择随机定向循环来创建均匀分布。我什至不知道这是否可能。

如有任何帮助，我们将不胜感激。

Answer 1

如果 N 很小(有 N^(2N) 组可能的弧满足前两个条件，所以您希望它小于随机数生成器的范围)，您可以生成随机 DFA 并丢弃不满足可达性条件的。