図で表される有限オートマトンで受理される文字列はどれか。
ここで →○ 初期状態を、◎ は受理状態を表す。
ア | 01011 |
イ | 01111 |
ウ | 10111 |
エ | 11110 |
答え ウ
【解説】
受理される文字列とは初期状態(→○)から入力されたデータ(文字)によって状態を遷移させて、最終的に受理状態(◎)になったもののことです。
有限オートマトンの問題は1つ1つ選択肢について、受理されるかどうかを調べます。
説明のため各状態に図のように名前(ラベル)をつけます。
状態Sからスタートして、データを処理し、最後のデータを処理したときの状態がGならば、そのデータは受理されることになります。
ア | この有限オートマトンで[01011]を処理するというのは、状態Sから0→1→0→1→1の順でデータを与えたときどういった状態の遷移を行うかです。 最初に状態Sで最初のデータ“0”を処理すると状態Sのままです。 次に状態Sで2番目のデータ“1”を処理すると状態Aに移ります。 次に状態Aで3番目のデータ“0”を処理すると状態Sに移ります。 次に状態Sで4番目のデータ“1”を処理すると状態Aに移ります。 最後に状態Aで5番目のデータ“1”を処理すると状態B移ります。 入力された文字列を全て処理しても状態Gにならなかったので、この文字列は受理されません。(エラーになります。) |
イ | [01111]の処理は、 最初に状態Sで最初のデータ“0”を処理すると状態Sのままです。 次に状態Sで2番目のデータ“1”を処理すると状態Aに移ります。 次に状態Aで3番目のデータ“1”を処理すると状態Bに移ります。 次に状態Bで4番目のデータ“1”を処理すると状態Gに移ります。 最後に状態Gで5番目のデータ“1”を処理すると状態Cに移ります。 このデータは途中で状態Gを通過しますが、最後の状態がGにならなかったので、この文字列は受理されません。 |
ウ | [10111]の処理は、 最初に状態Sで最初のデータ“1”を処理すると状態Aの移ります。 次に状態Aで2番目のデータ“0”を処理すると状態Sに移ります。 次に状態Sで3番目のデータ“1”を処理すると状態Aに移ります。 次に状態Aで4番目のデータ“1”を処理すると状態Bに移ります。 最後に状態Bで5番目のデータ“1”を処理すると状態Gに移ります。 入力された文字列を全て処理すると状態Gになったので、この文字列は受理されます。 |
エ | [11110]の処理は、 最初に状態Sで最初のデータ“1”を処理すると状態Aの移ります。 次に状態Aで2番目のデータ“1”を処理すると状態Bに移ります。 次に状態Bで3番目のデータ“1”を処理すると状態Gに移ります。 次に状態Gで4番目のデータ“1”を処理すると状態Cに移ります。 最後に状態Cで5番目のデータ“0”を処理すると状態Cのままです。 このデータは途中で状態Gを通過しますが、最後の状態がGにならなかったので、この文字列は受理されません。 |
【キーワード】
・有限オートマトン