finite-automata - NFA から DFA へのアルゴリズム

Question

シンボル、状態、および遷移のテキスト ファイルを読み取り、すべてを表にまとめました。
シンボル a、b
状態 q1、q2、q3、q4開始
状態 q4
最終状態 q2、q3

遷移状態:
q4、イプシロン、q1
q1、a、q2
q3、a、q3
q3、b、q1

NFA を DFA に変換する方法についてのアルゴリズムを読みましたが、アルゴリズムがよくわかりません。トランジション メソッドを作成するにはどうすればよいですか?また、状態クラスには何が必要ですか?

Answer 1

ここに気の利いたリンクがあります： JFLAP

JFLAP は Java JAR で、優れた視覚化が含まれています。NFA/DFA のテストと変換、ポンピング レンマ スタッフの実行、さまざまな文法のチェックなどを行うことができます。ぜひ試してみてください。

Answer 2

次の 2 つのリンクが役立ちます。

http://www.win.tue.nl/prose/pres/ploeger-19-10-06.pdf
http://www.cs.sun.ac.za/rw711/documentation/hopcroft2.pdf

Answer 3

プログラミングに問題がありますか、それとも Automata に問題がありますか?

これをプログラミングするのはとても簡単に思えるからです。はい、q1-a4 の 4 つの可能な値を持つ状態クラスがあります。状態クラスには、それを q4 に初期化する単一のコンストラクターがあります。状態オブジェクトを変更する Accept(symbol) 関数と、状態 q2 および q3 に対して true を返す IsEndState() 関数がある可能性があります。

NFA/DFA 部分は、Accept() メソッドの実装で機能します。ここで、Accept() の NFA ベースの実装を Accept() の DFA ベースの実装に変換するためのプログラムによる解決策を求められることがあります。

Answer 4

JFLAPのようなものをダウンロードせずに自動的に実行したい場合は、オンラインNFAからDFAへの変換ツールを試してみてください。

YouTubeのProfBrownの「ConvertNFAtoDFA」ビデオでは、厳密にそれを行う方法を検討していますが、IMOは、テーブルを手作業で作成する必要があるのは非現実的で不必要に面倒です。このプロセスに慣れるにつれて、小さなグラフを目で確認できるようになります。大きなグラフの場合は、とにかくそれを自動化するためのツールを使用します。