0
私は手書きレクサーをします。私は以前に作った3つの有限オートマトンを含む1つの非決定論的有限オートマトンを描く必要があります。飛行機、雲、滑走路などのキーワードを使って作成しました。私は助け、この3つのオートマトンの共通オートマトンを構築する方法が必要です。私はそれをする方法をいくつかの例が必要ですか？あなたが私を助けてください知っていれば??非決定的有限オートマトンを構築する
A
答えて
0
飛行機、雲、滑走路のオートマトンを描画して、開始状態の前に部屋を残します。さて、最初の状態を消去してください。新しい、単一の状態をその前に描画します。 "a"トランジション/エッジ、 "r"エッジを "離す"、 "c"エッジを "ラウド"にして "irplane"オートマトンに接続します。それでおしまい。完了しました。
もっと一般的なケースでは、それはより複雑です。 最初に、飛行機、雲、滑走路などの各オートマトンを描画します。開始位置によって空白が残ります。次に、開始する前の状態を描画し、それを自由端を介して飛行機、雲、滑走路オートマトンの初期開始状態の開始点に接続します。 （フリーエッジは、εエッジ、イプシロンエッジ、λエッジ、またはラムダエッジとも呼ばれます）。
次に、あなたはyoutubeのビデオチュートリアルを見つけることができるサブセット構築アルゴリズムを実行します。 online subset construction algorithm toolもあり、非決定論的有限オートマトンを確定的有限オートマトン（DFA）に変換します。このプロセスを「決定」といいます。
DFAを取得したら、それを使用して、スキャナを駆動する状態、アクション、およびルックアップテーブルを構築します。これは、独自のワームの缶です。人々は通常、それを自動化するためにLexやFlexのようなスキャナジェネレータを使います。オンラインで使用できる同様の、使いやすいツールはthe Online Scanner Generatorです。あなたは、次の入力を提供することで、グラフを作ってそれを使用することができます。
airplane:airplane
cloud:cloud
runway:runway
それはそうのように、そのためにあなたにDFAをあげる：