簡単なステートメントが与えられます:alphabet {0, 1}を受け入れるDFA を構築しますall the strings that end in 101。
私の質問は、それを設計するためのステップは何ですか? または、NFA を設計します。NFA を DFA に変換する明確な手順を知っているので、NFA を DFA に変換します。
注:- これは私にとってはマイナーなコースなので、正規表現や、おそらく DFA の構築に使用されるアルゴリズムなどを勉強したことはありません。
10052 次
1 に答える
4
これをどのように導き出したかについてもっと説明が必要な場合は、喜んで説明しますが、今のところ、DFA を描画し、各状態を説明しました。
スクリーンショットについて申し訳ありません...それを直接画像に変換する方法がわかりませんでした。
状態 0 の入力 0 では、それ自体にループ バックします。1 の場合、「101」になる可能性があるため、終了する準備をします。
q1 は、'101' で終了する準備をしているため、入力 1 で自分自身にループします。q1 の入力「0」は、入力「10」の準備中であることを意味するため、q2 に進みます。
q2 に「0」を入力すると、サイクル全体が中断され、q0 に戻ります。「1」を入力すると、受け入れ状態であるq3に移動します。
q3 への入力は、入力が対応するサイクルの任意のポイントに戻ります。
つまり、'1' で q1、つまり '101' で最初の '1' に遭遇した状態に戻り、終了の準備をします。
「0」では、q2 に進みます。q3 に到達するには、q2 から「1」の入力があったに違いないため、最後の 2 つの入力シンボルは現在「10」です。
于 2014-04-24T17:30:08.837 に答える