什么是生成随机DFA的好算法？

Question

我正在生成随机DFA，以测试它们的DFA还原算法。

我现在使用的算法如下：对于每个状态$ q $，对于字母$ c $中的每个符号，将$ delta（q，c）$添加到某个随机状态。每个州都具有成为最终状态的概率。

这是生成无偏DFA的好方法吗？另外，该算法不会生成TRIM DFA（没有过时状态的DFA），所以我想知道是否有更好的方法可以确保它是装饰的，可以确保它以某种方式确保它？

Answer 1

查看[1]和第4节中的讨论，随机自动机生成。该纸基测试了不同的DFA最小化算法。使用统一的随机生成器，该生成器生成具有$ N $状态和$ K $符号的完整DFA的规范字符串表示。他们还讨论其他方法。

---

[1] Almeida，M.，Moreira，N。，＆Reis，R。（2007）。关于自动机最小化算法的性能。算法的逻辑和理论，3。

Answer 2

你应该看 西里尔·妮德（Cyril Nicaud）的主页。特别是，以下引用与您的问题有关：

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

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

Answer 3

有算法可以随机生成DFA，直到置换 http://paranthoen.thomas.free.fr/papers/randdfatoappearintcs.ps.gz.

但是，在上文中也提到，几乎所有DFA都已经很少。非最小DFA就像质数一样……只有很少的。而且，如果您使用此算法来测试最小化算法，则就像您正在使用简单的随机数生成器测试质数上的算法。为了具有更多的非最小DFA，您可以通过添加下沉状态来更改算法，并将重要百分比转移到该下沉状态。

但是从我的角度来看，如果您想测试实现的迅速性，请根据要使用的内容来检查它：使用随机单词集或随机正则言论，创建NFA或DFA，然后最小化生成的DFA 。

Answer 4

一种自然策略是将DFA视为图形，然后有许多“自然”和经过深入研究的随机分布，最简单的是 Erdos-Renyi. 。在这种情况下，选择了DFA的所有状态为图的节点，并且选择了所有可能的边缘（DFA过渡）的固定百分比。在最近的时代进行了很多研究的更复杂的分布是 小世界 图。对于您在问题中提到的策略，您显然选择了特殊情况$ p = 1/n $，其中$ n $是图中的节点数量。但是，您的策略或Erdos-renyi也不能保证DFA中的所有州都连接[自然限制]。