レクサーに DFA ミニマイザーを実装しようとしていますが、式の最小 DFA であるとは思えない DFA を生成することはできません。
後置正規表現からトムソン構築を使用して構築された NFA から DFA を構築しています。ドラゴンブックに書かれていることとほぼ同じです。レクサーを作成するために、いくつかの NFA が開始状態からのイプシロン遷移を使用して結合されます。DFA アルゴリズムが適用されるのは、この結合された NFA です。
では、デッドステートの除去とステートの最小化のための優れたテストベッドとなる DFA を生成する「既知の」正規表現はありますか?
もちろん、奇妙な DFA をハックしてそれにアルゴリズムを適用することもできますが、それは実際には適切なテスト ケースではないでしょうか? 私が構築している DFA のメソッドがデッド ステートになりにくいようにするためである場合、その情報は同様に価値があります。その場合、ステート エリミネーション機能の実装を完全にスキップできるからです。
編集：正確に答えるために実装の詳細が必要な場合は、コードはgithub、特にNFA.csおよびDFA.csクラスで入手できます。さらに、私が使用している構築アルゴリズムに関する一連のブログ記事を書いています。