明らかな選択は、すべての可能な入力を使い果たすことです。私はやったと思います。しかし、それが有効かどうかはよくわかりません。また、非決定性有限オートマトンの規則に違反していません。
私のNFAは次のように与えられます：(ab u aab u aba)*そして以下は私の図です。
私は何かを逃したことがありますか？
1473 次
1 に答える
1
何も欠けているわけではありませんが、パスを折りたたんで λ ルールを削除することで、NFA を大幅に簡素化できます。NFA が正規表現で表される言語を決定するかどうかを判断するために、遷移グラフで状態を追跡することによって非公式に議論できます。NFA について説明するために、最終状態 {q 0 ,q 3 ,q 4 } と初期状態 q 0を持つ δ 関数の次の定義を使用します。
- δ(q 0 ,a) = {q 1 ,q 2 }
- δ(q 1 ,a) = {q 2 }
- δ(q 2 ,b) = {q 3 }
- δ(q 3 ,a) = {q 4 }
- δ(q 3 ,λ) = {q 0 }
- δ(q 4 ,λ) = {q - }
目標は、NFA が言語 (ab U aab U aba)* を正確に受け入れることを示すことです。この目的のために、q 0の λ で始まり、グラフを介してすべての可能な遷移を使い果たし、遷移されたシンボルを連結することによって構築された文字列を記録し、そのような文字列が受け入れられるかどうかに注意することによって受け入れられる文字列を考えることができます。グラフのパスは連結を示します。最終状態は、受け入れまたは分離を示します。ループはクリーネ星を示します。
q 0と λから、aで q 1または q 2に遷移できます。q 1とaで、q 2に遷移できます。したがって、q 2には、 aまたはaaのいずれかがあり、他には何もありません。q 2とaまたはaaから、 bで q 3に遷移できます。したがって、q 3には、 abまたはaabのいずれかがあり、他には何もありません。q 3とabまたはaabから q に遷移できますλ の0またはaのq 4。したがって、q 3とabまたはaabには、abまたはaabまたはabaのいずれかがあり、他には何もありません。最後に、q 4とabaで、λで q 0に遷移できます。ab、aab、またはabaがあり、開始状態に遷移したため、派生が 0 回以上繰り返される可能性があり、可能な遷移を使い果たしたので、NFA がab、aab、またはabaの Kleene 閉包を決定すると結論付けます。.
特定の NFA が言語を決定することを示す、より正式な方法があります。しかし、最も簡単な方法は、NFA を介してすべての可能なパスを使い果たし、サイクルに Kleene クロージャを導入することです。正式な方法の例は、NFA を正規表現に変換し、取得した式とターゲット式の等価性を公理的に導き出すことです。これはほとんど不要です。
おそらく、私が今書いたことを正確に行っていると思いますが、この投稿全体が不要になっています. そうでない場合は、NFA が言語を決定することを自分自身に納得させるために使用できる非公式の推論を示してくれることを願っています.
于 2011-10-21T05:16:39.620 に答える