DFA必须具备以下四个属性:
有人知道如何完成该算法吗?或者,有人知道另一个算法吗?我似乎模糊地记得二叉树可以用来构造这个,但我不确定。
DFA有N个节点
每个节点有2个出边。
每个节点可以从任何其他节点到达。
DFA是从所有可能性中完全随机选择的。
- 从N个节点的集合开始。
- 选择一个尚未被选择的节点。
- 将其输出连接到另外两个随机选择的节点上。
- 标记一个转换为1,另一个转换为0。
- 除非所有节点都已被选择,否则回到第2步。
- 确定是否存在没有入边连接的节点。
- 如果有,则从具有多于1个入边连接的节点中窃取一个入边连接。
- 否则,进入第6步,直到没有没有入边连接的节点。
1 <==> 2
3 <==> 4
在此处,<==> 表示双向出边(总共4条边)。这似乎形成了2个团,这意味着并非每个状态都可以从任何其他状态到达。有人知道如何完成该算法吗?或者,有人知道另一个算法吗?我似乎模糊地记得二叉树可以用来构造这个,但我不确定。