DFA 必须具有以下四个属性:
DFA 有 N 个节点
每个节点有 2 个传出转换。
每个节点都可以从其他每个节点访问。
DFA 是从所有可能性中以完全一致的随机性选择的
这是我到目前为止所拥有的:
- 从 N 个节点的集合开始。
- 选择一个尚未选择的节点。
- 将其输出连接到其他 2 个随机选择的节点
- 将一个转换标记为 1,将另一个转换标记为 0。
- 转到 2,除非已选择所有节点。
- 确定是否存在没有传入连接的节点。
- 如果是这样,从具有超过 1 个传入连接的节点窃取传入连接。
- 转到 6,除非没有没有传入连接的节点
但是,这是算法不正确的。考虑图中节点 1 有两个连接到节点 2(反之亦然),而节点 3 有两个连接到节点 4(反之亦然)。那是这样的:
1 <==> 2
3 <==> 4
其中,<==> 我的意思是双向两个传出连接(因此总共有 4 个连接)。这似乎形成了 2 个派系,这意味着并非每个州都可以从其他州到达。
有谁知道如何完成算法?或者,有人知道另一种算法吗?我似乎隐约记得可以使用二叉树来构造它,但我不确定。