DFA最小化テストスイート？

Question

私は、DFA最小化アルゴリズムの正確性をテストするために使用される確定的有限オートマトンのテストスイートを探しています。いくつか指摘していただけますか？または、そのようなオートマトンを生成するアルゴリズム/実装がありますか？

は恵みを獲得するためには、様々なサイズと複雑さの400以上の非最小限のオートマトン、2000個の以上のノードを含む少なくとも20のテストスイートを提出する必要があります。

これは、この質問をするために適切な場所ではない場合、いくつかのより良い場所に私を指示してください。ありがとう。

Answer 1

正確性をテストするには、最小DFAをOpenFst形式に変換し、equivalence操作を使用して最小化されたaccetporsの等価性をテストします。

Answer 2

テスト「のすべて」のDFA n個の状態とm個のアルファベットの記号までは実行不可能です。既知の最小DFAを使用してDFAをテストできます。 （DFA、最小DFA）のペアを得るには、ランダムなREを生成し、Kleeneの定理からアルゴリズムを使ってNFA-lambdaを取得し、サブセット構造を使用してDFAを取得し、DFA最小化の既知の正しいアルゴリズムで最小化します正準アルゴリズムが正しいことを受け入れる）。

EDIT：

ここで、私が言ったことに拡張するためには、私は非最小限の有限オートマトンのテストスイートを生成しようとする方法は次のとおりです。

1. はN・オペレーション（連結を使用して正規表現を生成し、組合、クローネ閉鎖）。
2. O（N）でNFA-lambdaを取得するためにクリーネの定理からアルゴリズムを使用し、それに述べています。
3. サブセット/パワーセット構造を使用して、O（2^n）状態のDFAを取得します。
4. 充分に複雑なオートマトンが見つかるまで、繰り返します。正規表現を生成

は簡単です。いくつかのルールがあります：アルファベット記号

ある場合

1. REである（RS）は、R、SはREの
2. （R + S）である場合にREであるR場合REであります、sがあるのRE
3. （R *）がREであるrはRE
4. であれば他に何もn個の操作でREを取得するために、RE

ではありません、再帰的なアプローチが動作します。

GetRE(ops) 
1. if ops = 0 then return RandomAlphabetSymbol() 
2. select(Rand() % 3) 
3. case 0 then 
4. ops1 = Rand() % (ops - 1) 
5. ops2 = (ops - 1) - ops1 
6. return "(" + GetRE(ops1) + "+" + GetRE(ops2) + ")" 
7. case 1 then 
8. ops1 = Rand() % (ops - 1) 
9. ops2 = (ops - 1) - ops1 
10. return "(" + GetRE(ops1) + "." + GetRE(ops2) + ")" 
11. case 2 then 
12. return "(" + GetRE(ops - 1) + "*)" 

あなたは非文字列表現を見つけるかもしれないが（すなわち、階層リンク構造は、基本的に解析ツリー自体は）NFA-ラムダを得るためにクリーネのアルゴリズムを適用するためのより便利なオプションです。