ランダムDFAを生成するための良いアルゴリズムは何ですか？

Question

DFA削減アルゴリズムをテストするためにランダムDFAを生成しています。

私が現在使用しているアルゴリズムは次のとおりです。各状態$ q $について、アルファベット$ c $の各シンボルについて、$ delta（q、c）$をランダム状態に追加します。各州には、最終状態になる可能性が同じです。

これは、公平なDFAを生成する良い方法ですか？また、このアルゴリズムは、トリムDFA（時代遅れの状態のないDFA）を生成しないので、それが何らかの形でトリムであることを保証できるランダムDFAを生成するより良い方法があるかどうか疑問に思っていますか？

Answer 1

セクション4のランダムオートマトン生成の議論[1]とディスカッションをご覧ください。ペーパーベンチマークは、異なるDFA最小化アルゴリズムです。 $ n $状態と$ k $シンボルを備えた完全なDFAの標準文字列表現を生成する均一なランダムジェネレーターが使用されています。また、他の方法についても説明します。

---

[1] Almeida、M.、Moreira、N。、＆Reis、R。（2007）。 Automata Minimization Algorithmsのパフォーマンスについて。アルゴリズムの論理と理論、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

1つの自然な戦略は、DFAをグラフと見なすことであり、グラフの多くの「自然な」ランダム分布があります。 erdos-renyi. 。その場合、DFAのすべての状態をグラフのノードとして扱い、可能なすべてのエッジ（DFA遷移）の一部の固定パーセントが選択されます。より最近の時代に多く研究されているより洗練された分布は 小さな世界 グラフ。質問で言及する戦略については、明らかに特別なケース$ p = 1/n $を選択しているようです。ここで、$ n $はグラフのノードの数です。しかし、あなたの戦略もerdos-renyiも、DFAのすべての州が接続されていることを保証しません[追加する自然な制約]。