DFA最小化Brzozowskiアルゴリズム

Question

DFAを最小化するためにBrzozowskiのアルゴリズムを実装しようとしています 以下はそのためのアルゴリズムです。 ジェネラコディセタグプレ

ここで、r()はNFAの反転であり、D()はNFAをDFAに変換します。

しかし、私はグーグルで検索するr()の意味が何であるかを理解していません。また、多くの情報を提供しません。

NFAのジェネラコダイスタグコードとは何か説明してもらえますか。

利用可能な他の単純なアルゴリズムまたはC ++実装があれば、リンクを教えてください。

Answer 1

reverse.cのコード内（ ここ ですが、現在は機能していません）コメント/* Create reversed edges */があります。したがって、r()はすべてのエッジの方向を反転していると言えます（さらに、反転したオートマトンの開始状態が明確に定義されていることを確認してください）。

Answer 2

これはOpenFst。

このの論文は図（15ページ）です。逆の操作を適用した結果を表示します。

FSMの操作を理解するためのより簡単な方法は、OpenFstなどのライブラリを使用してマシンを作成および操作し、Graphvizを使用して結果を視覚化することです。