regex - 正規表現を有限オートマトンに変換するにはどうすればよいですか?

Question

次の正規表現を有限オートマトンに変更するにはどうすればよいですか?

(abUb)(bUaaa)b*b((a*b)*Ub)*

注: この場合、U は結合を意味します

Answer 1

この正規表現には、5 つの最上位連結コンポーネントがあります。クリーネの定理の一部から回復可能なアルゴリズムに従って、これらの NFA ラムダを作成し、1 つの最終状態を次の初期状態に接続して連結を形成できます。

ユニオンとは、2 つのマシンを作成し、2 つのラムダ遷移を持つ新しい開始状態を作成してそれらを結合することを意味します。

Kleene クロージャはもう少し複雑ですが、基本的には、繰り返されるもののためにマシンを作成し、新しい受け入れ開始状態と古い最終状態からのループを追加して変換します。

基本ケースは、適切にラベル付けされた遷移を持つ、初期と最終の 2 つの状態である単一の文字のマシンです。

最も単純なマシン (最も内側の部分式) から全体を再帰的に処理し、必要に応じて組み合わせます。必要に応じて結果を単純化し、最小限の DFA に変換します。

Answer 2

Automatic Java Code Generator for Regular Expressions and Finite Automata と呼ばれるアプリケーションがあり、特定の正規表現または有限オートマトンの NFA、DFA (遷移テーブルを含む)、および Java コードを自動的に生成します。次のリンクからダウンロードできます: www.s-solutions.infoソリューションが正しいかどうかはいつでも確認できます。