平成26年度 春期 応用情報技術者試験 午前 問4
テクノロジ／基礎理論表は，入力記号の集合が{0，1}，状態集合が{a，b，c，d}である有限オートマトンの状態遷移表である。長さ3以上の任意のビット列を左（上位ビット）から順に読み込んで最後が110で終わっているものを受理するには，どの状態を受理状態とすればよいか。 状態：入力0の遷移先：入力1の遷移先 a：a：b b：c：d c：a：b d：c：d （注：本サイトでは原問題の表を文字表記に変換しています）
出典：平成26年度 春期 応用情報技術者試験 午前 問4
- アa
- イb
- ウc
- エd
正解：ウ
解説
状態遷移表に従い「1」「1」「0」の順に読むと，状態aから読み進めた場合a→(1)→b→(1)→d→(0)→cとなり，直前の2ビットが「1，1」の状態（d）から「0」を読むと必ず状態cに遷移する。したがって，ビット列の末尾が110で終わっているときに到達する状態はcであり，これを受理状態とすればよい。
選択肢ごとの解説
- ア誤り。aは初期状態であり，110を読み終えた直後に到達する状態ではない。
- イ誤り。bは「1」を1回読んだ直後などに現れる状態であり，末尾が110のときに到達する状態ではない。
- ウ正しい。直前の2ビットが「1，1」であることを表す状態dから「0」を読むとcに遷移するため，末尾が110で終わるビット列は必ずcに到達する。
- エ誤り。dは直前の2ビットが「1，1」であることを示す状態であり，最後の0を読む前の状態である。