次の言語を受け入れる決定論的有限オートマトンを構築したいと考えています。
{w ∈ {a,b}* : w の各 a の直前に ab がある}
これまでのところ >⨀ ---b---> O ---a---> O.
'>' = 初期状態
⨀ = 最終状態
1413 次
2 に答える
6
FA について考える良い方法は、どのように言語の文字列にたどり着くかという観点から、いくつの異なる状況に陥り得るかを考えてみることです。いくつかの小さな文字列から始めて、私が何を意味するか見てみましょう。
空の文字列から始めるとします。言語の文字列を取得するには、これに何を追加できますか? 空文字列は言語にあるので、空文字列を追加して (つまり、何もない)、言語にも文字列を含めることができます。さらに、目的の言語の任意の文字列を空の文字列に追加することができ、その言語の文字列を (簡単に) 取得します。空の文字列 (およびそのような文字列 - 言語の空の文字列またはその他の文字列を追加しても言語に文字列が残っている文字列) を記憶するには、少なくとも 1 つの状態が必要です。これが開始/初期状態になり、空の文字列が言語にあるため (これは簡単に確認できます)、開始/初期状態が受け入れられることがわかります。
では、文字列 a について考えてみましょう。これは言語にない文字列の例であり、この文字列の末尾に何も追加して言語に含めることはできません。文字列内のすべての a の前に b があるという条件にすでに違反しています。言語で文字列を取得するためにこれに追加できる文字列のセットは空のセットであるため、この文字列とそれに似た文字列を記憶するために、既に識別した状態とは異なる状態が必要になります。言語で文字列を取得するために何も追加することはできません。
要約すると、2 つの状態を識別しました。受け入れ開始/初期状態と、「デッド」状態と呼ばれるもの - 受け入れておらず、受け入れ状態に至らない状態です。
文字列 b を試してみましょう。この文字列は言語に含まれているため、空の文字列を追加できます。この文字列の末尾に言語の他の文字列を簡単に追加して、その言語の別の文字列を取得することもできます。ただし、言語の任意の文字列が続く a を追加して、その言語の別の文字列を取得することもできます。たとえば、文字列 a の後に bbbabb を追加して babbabb を取得できます。これも言語内にあります。したがって、追加できる文字列のセットは、これまでに見たことのないセットであり、この文字列 (文字列 b) とそのような文字列を表す新しい状態が必要になります。文字列 b は言語の文字列であるため、受け入れられます。
文字列 aa、ab、ba、および bb を試してください。文字列 aa と ab の両方が既にデッド状態に含まれていることがわかります (これらの文字列の末尾に文字列を追加して言語で何かを取得することはできません)。文字列 ba は start/initial によってカバーされています。状態 (言語内の他の文字列を取得するために、既に言語内にあるこの文字列にのみ追加できます)、その bb は、識別した 3 番目の状態に対応します (任意の文字列を追加するか、単一の a の後に任意の文字列を追加すると、結果として a文字列も言語で）。長さ 2 のすべての文字列を使い果たし、新しい状態を追加していないため、FA で必要なすべての状態であることがわかります。他にも追加できますが、それらは不要です。
遷移を取得するために必要なことは、すべての状態が正しい場所につながることを確認することだけです。つまり、文字列 a は空文字列の末尾に文字 a を追加することによって形成されるため、開始/初期状態 (空文字列に対応) からデッド状態 (文字列 a に対応) への遷移が必要です。 ) FA がシンボル a を読み取るときに発生します。同様に、シンボル b の開始/初期状態から 3 番目の状態への遷移が必要です。他の遷移も同様に検出されます。a または ab のいずれかで、dead 状態がそれ自体に遷移し、3 番目の状態が b でループし、a で start/initial 状態に遷移します。各状態にアルファベットの各記号の遷移があると、完全な (そして正しい) FA が得られます。しかも、このように構築することで、
于 2011-09-21T20:42:02.707 に答える
1
状態 1 (受け入れ、初期状態):
- 入力 'a' で、状態 3 に移動します (文字列を永久に拒否します)。
- 入力 'b' で状態 2 に進む
状態 2 (受け入れ中):
- 入力 'a' で状態 1 に移動
- 入力 'b' で状態 2 に進む
状態 3 (受け入れていない)
- 入力 'a' または 'b' で、状態 3 に留まる
概念的には、状態 1 は「最後の文字が b でない有効な文字列」を表し、状態 2 は「最後の文字が b である有効な文字列」を表し、状態 3 は「無効な文字列」を表します。
グラフ形式:
于 2011-09-21T20:17:26.127 に答える