平成26年度 春期 応用情報技術者試験 午前 問4

最後の3ビット「110」を読んだときに，それ以前の状態に関係なく同じ状態に到達するかを調べます。

1. 「1」を読む：a→b，b→d，c→b，d→d なので，状態は b か d になります。
2. 続けて「1」を読む：b→d，d→d なので，状態は必ず d になります。
3. 続けて「0」を読む：d→c なので，状態は c になります。

したがって，110で終わるビット列を読み込むと，それ以前のビットに関係なく必ず状態 c になります。c を受理状態とすればよいことになります。

• ア: a
  誤り。状態 a は，最後の2ビットが「00」のときなどに到達する状態で，110で終わる列の到達先ではありません。

• イ: b
  誤り。状態 b は，最後のビットが1で，その前が0（または先頭）のときの状態です。

• ウ: c
  正しい。110で終わるビット列を読み込むと必ず状態 c に到達するので，c を受理状態とします。

• エ: d
  誤り。状態 d は，最後の2ビットが「11」のときの状態です。

答え

ウ: c