平成18年 秋期 基本情報技術者 午前 問11

図で表される有限オートマトンで受理される文字列はどれか。
ここで →○ 初期状態を、◎ は受理状態を表す。

 ア  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にならなかったので、この文字列は受理されません。


キーワード
・有限オートマトン

キーワードの解説

戻る 一覧へ 次へ