4

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

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

4

7 回答 7

4

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

生成满射转换函数本身就很重要。不幸的是，如果没有这个约束，每个状态都不太可能有一个传入的转换。使用该问题的答案中描述的算法对 {(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
于 2011-04-03T19:20:22.653 回答
1

在下文中，我将使用图论的基本术语。

你可以：

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

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

于 2011-04-02T20:43:53.457 回答
1

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

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

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

于 2015-04-24T14:20:53.957 回答
0

只需继续增长一组都可以访问的节点。一旦它们都可以到达，请填写空白。

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中的一个节点，它就可以被添加到集合中。

于 2011-04-02T20:48:21.570 回答
0

我能想到的最简单的方法是（统一地）生成一个随机 DFA，其中包含N节点和每个节点的两个传出边，忽略其他约束，然后丢弃任何非强连接（使用强连接很容易测试）连通分量算法）。生成统一的 DFA 应该很简单，没有可达性约束。在性能方面可能存在问题的一件事是在找到具有可达性属性的 DFA 之前需要跳过多少个 DFA。不过，您应该先尝试这个算法，然后看看最终生成可接受的 DFA 需要多长时间。

于 2011-04-03T19:15:24.203 回答
0

以下参考资料似乎与您的问题有关：

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

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

于 2013-08-24T08:51:46.183 回答
0

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

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

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

如果我们也希望有一个最小自动机，那么只剩下最终状态的分配，但是随机分配也很有可能得到一个最小自动机。

于 2012-03-30T16:03:42.297 回答