4

我需要从满足以下属性的所有可能的 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，但是，我不知道如何选择随机定向循环来创建均匀分布。我什至不知道这是否可能。

任何帮助将不胜感激。

4

1 回答 1

1

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

于 2011-04-03T22:41:38.490 回答