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

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) 次迭代。

生成满射过渡函数本身就很重要。不幸的是，如果没有这个约束，每个状态都有传入转换的可能性呈指数级增长。使用此问题的答案中描述的算法对包含 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

Answer 2

接下来，我将使用图论的基本术语。

您可以：

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

结果将满足所有三个要求。

Answer 3

有一个预期运行时间为 O(n^{3/2}) 的算法。

如果生成具有 m 个顶点的均匀随机有向图，使得每个顶点都有 k 个标记的外弧（k 出有向图），则该有向图中最大的 SCC（强连通分量）的大小很有可能约为 c_k m，其中 c_k 是取决于 k 的常数。实际上，该 SCC 的大小恰好为 c_k m（四舍五入为整数）的概率约为 1/\sqrt{m}。

因此，您可以生成大小为 n/c_k 的均匀随机 2-out 有向图，并检查最大 SCC 的大小。如果它的大小不正好是n，就再试一次，直到成功。所需的预期试验次数为 \sqrt{n}。生成每个有向图应该在 O(n) 时间内完成。因此，算法总共预计运行时间为 O(n^{3/2})。有关更多详细信息，请参阅本文。

Answer 4

只需不断增长一组全部可达的节点即可。一旦都可以到达，请填写空白。

Start with a set of N nodes called A.
Choose a node from A and put it in set B.
While there are nodes left in set A
    Choose a node x from set A
    Choose a node y from set B with less than two outgoing transitions.
    Choose a node z from set B
    Add a transition from y to x.
    Add a transition from x to z
    Move x to set B
For each node n in B
    While n has less than two outgoing transitions
         Choose a node m in B
         Add a transition from n to m
Choose a node to be the start node.
Choose some number of nodes to be accepting nodes.

集合B中的每个节点都可以到达集合B中的每个节点。只要从集合B中的节点可以到达某个节点并且该节点可以到达集合B中的节点，则可以将其添加到集合中。

Answer 5

我能想到的最简单的方法是（统一）使用n节点和每个节点两个传出的边缘生成一个随机的DFA，忽略其他约束，然后丢弃任何没有强烈连接的（使用牢固连接的组件算法易于测试）。生成均匀的DFA应该是直接的，而无需限制。在性能方面，可能是有问题的一件事是，在找到具有可及性属性的DFA之前，您需要跳过多少个DFA。但是，您应该首先尝试此算法，并查看生成可接受的DFA的最终需要多长时间。

Answer 6

我们可以从 N 到 2N 之间的随机状态数 N1 开始。

假设初始状态为状态号1。
对于每个状态，对于输入字母表中的每个字符，我们生成一个随机转换（1 到 N1 之间）。

我们从初始状态开始获取连接自动机。我们检查状态的数量，经过几次尝试，我们得到了一个具有 N 个状态的状态。

如果我们也希望有一个最小自动机，则仅保留最终状态的分配，但是随机分配也很有可能获得最小自动机。

Answer 7

以下参考文献似乎与您的问题相关：

F. Bassino、J. David 和 C. Nicaud，可能不完整的确定性自动机的枚举和随机生成，纯数学和应用 19(2-3)(2009)1-16。

F. Bassino 和 C. Nicaud。可访问自动机的枚举和随机生成。 理论。比较。 Sc.。 381 (2007) 86-104。