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

Question

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 个派系，这意味着并非每个州都可以从其他所有州到达。

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

Answer 1

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

生成满射转换函数本身就很重要。不幸的是，如果没有这个约束，每个状态都有一个进入的转换是不可能的。使用 this question 的答案中描述的算法对 {(1, a), (1, b), (2, a), (2, b), …, (N, a), (N, b)} 的均匀随机分区进行采样，其中包含 N 个部分。随机排列节点并将它们分配给零件。

例如设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