是什么算法用于产生随机确定型有限自动？ [英] What is the algorithm for generating a random Deterministic Finite Automata?
问题描述
在DFA必须具备以下四个属性：
The DFA must have the following four properties:
-
在DFA有N个节点
The DFA has N nodes
每个节点都有2个向外的转移。
Each node has 2 outgoing transitions.
每个节点与所有其他节点的访问。
Each node is reachable from every other node.
DFA的选择有完全一致的随机性，从所有的可能性
The DFA is chosen with perfectly uniform randomness from all possibilities
这是我到目前为止有：
- 在开始有N个节点的集合。
- 选择还没有已被选择的一个节点。
- 在其输出端连接到其他2随机选择的节点
- 标签一个转换1，另一个过渡0。
- 转至2，除非所有的节点都被选中。
- 确定是否存在没有传入的连接的节点。
- 如果是这样，偷一个节点拥有超过1传入连接传入连接。
- 进入6，除非有没有节点，没有传入的连接
然而，这算法是不正确的。考虑图，其中节点1具有其两个连接去到节点2（反之亦然），而节点3具有其两个连接去到节点4（反之亦然）。这是一样的东西：
However, this is algorithm is not correct. Consider the graph where node 1 has its two connections going to node 2 (and vice versa), while node 3 has its two connection going to node 4 (and vice versa). That is something like:
1 LT; ==> 2
1 <==> 2
3'; ==> 4
3 <==> 4
在哪里，以＆lt; ==>我的意思是两位即将离任的连接两种方式（因此总共有4个连接）。这似乎形成2派系，这意味着不是每个状态是从每一个其他状态可到达的。
Where, by <==> I mean two outgoing connections both ways (so a total of 4 connections). This seems to form 2 cliques, which means that not every state is reachable from every other state.
有谁知道如何完成的算法？或者说，没有人知道另外的算法？我似乎隐约记得，二叉树可以用来建造这一点，但我不知道这一点。
Does anyone know how to complete the algorithm? Or, does anyone know another algorithm? I seem to vaguely recall that a binary tree can be used to construct this, but I am not sure about that.
推荐答案
强连接是一个困难的约束。让我们产生均匀随机的满射的转换函数，然后用，例如测试它们的Tarjan的线性时间SCC算法，直到我们得到一个，强烈连接。这个过程有正确的分布，但目前还不清楚它的效率更高;我的研究人员的直觉是，强连接性的限制概率小于1但大于0，这将意味着只有O（1）的迭代是必要的，期望
Strong connectivity is a difficult constraint. Let's generate uniform random surjective transition functions and then test them with e.g. Tarjan's linear-time SCC algorithm until we get one that's strongly connected. This process has the right distribution, but it's not clear that it's efficient; my researcher's intuition is that the limiting probability of strong connectivity is less than 1 but greater than 0, which would imply only O(1) iterations are necessary in expectation.
生成满射转变职能本身是平凡的。不幸的是，没有这种约束是指数不太可能每一个国家都有一个进来的过渡。使用的答案中描述的算法<一个href="http://stackoverflow.com/questions/2161406/how-do-i-generate-a-uniform-random-integer-partition">this问题以采样的均匀随机分区{（1，一），（1，b）中，（2，一），（2，B），...，（N，A），（N，B） }有N个部分。置换节点随机并将其分配给部分。
Generating surjective transition functions is itself nontrivial. Unfortunately, without that constraint it is exponentially unlikely that every state has an incoming transition. Use the algorithm described in the answers to this question to sample a uniform random partition of {(1, a), (1, b), (2, a), (2, b), …, (N, a), (N, b)} with N parts. Permute the nodes randomly and assign them to parts.
例如，让N = 3并假设随机分区是
For example, let N = 3 and suppose that the random partition is
{{(1, a), (2, a), (3, b)}, {(2, b)}, {(1, b), (3, a)}}.
我们选择一个随机排列2，3，1并从中获得一个转换函数
We choose a random permutation 2, 3, 1 and derive a transition function
(1, a) |-> 2
(1, b) |-> 1
(2, a) |-> 2
(2, b) |-> 3
(3, a) |-> 1
(3, b) |-> 2
这篇关于是什么算法用于产生随机确定型有限自动？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
