生成随机确定性有限自动机的算法是什么？

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

• DFA 有 N 个节点

• 每个节点有 2 个传出转换。

• 每个节点都可以从其他每个节点访问。

• 从所有可能性中以完全一致的随机性选择 DFA

这是我到目前为止所拥有的：

1. 从 N 个节点的集合开始。
2. 选择一个尚未选择的节点。
3. 将其输出连接到另外 2 个随机选择的节点
4. 将一个转换标记为 1，将另一个转换标记为 0。
5. 除非已选择所有节点，否则转至 2。
6. 确定是否存在没有传入连接的节点。
7. 如果是这样，则从具有超过 1 个传入连接的节点窃取传入连接。
8. 转至6，除非不存在没有传入连接的节点

然而，这个算法是不正确的。考虑该图，其中节点 1 有两个连接到节点 2（反之亦然），而节点 3 有两个连接到节点 4（反之亦然）。那是这样的：

1 2

3 4

其中， 是指​​双向两个传出连接（因此总共 4 个连接）。这似乎形成了 2 个派系，这意味着并非每个状态都可以从其他状态到达。

有谁知道如何完成算法吗？或者，有人知道另一种算法吗？我似乎隐约记得二叉树可以用来构造这个，但我不确定。

强连通性是一个困难的约束。让我们生成均匀随机数满射的转换函数，然后用例如测试它们Tarjan 的线性时间 SCC 算法，直到我们得到强连接的算法。这个过程有正确的分布，但不清楚它是否有效；我的研究人员的直觉是，强连通性的极限概率小于 1 但大于 0，这意味着预期只需 O(1) 次迭代。

生成满射过渡函数本身就很重要。不幸的是，如果没有这个约束，每个状态都有传入转换的可能性呈指数级增长。使用答案中描述的算法这个问题 https://stackoverflow.com/questions/2161406/how-do-i-generate-a-uniform-random-integer-partition对包含 N 个部分的 {(1, a), (1, b), (2, a), (2, b), …, (N, a), (N, b)} 的均匀随机分区进行采样。随机排列节点并将它们分配给部分。

例如，令 N = 3 并假设随机划分为

{{(1, a), (2, a), (3, b)}, {(2, b)}, {(1, b), (3, a)}}.

我们选择随机排列 2, 3, 1 并导出一个转换函数

(1, a) |-> 2
(1, b) |-> 1
(2, a) |-> 2
(2, b) |-> 3
(3, a) |-> 1
(3, b) |-> 2