答え ウ
【解説】
受理される文字列とは初期状態(→○)から入力されたデータ(文字)によって状態を遷移させて、最終的に受理状態(◎)になったもののことです。
有限オートマトンの問題は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にならなかったので、この文字列は受理されません。 |