問4応用情報技術者 平成28年度 秋期

解説

正解は3。表を読むと、入力0ではa・cからa、b・dからcへ移り、入力1ではa・cからb、b・dからdへ移る。つまり行き着く状態は直前の2ビットだけで決まり、aは00、bは01、cは10、dは11で終わったときの状態になる。末尾が110なら、1を読んでbかd、次の1でd、最後の0でcとなり、それより前に何があっても必ずcに行き着く。110で終わる列をすべて受理できるのはcを受理状態にしたときだけなので、3が正しい（cには010で終わる列も行き着くので、厳密には末尾10の判定になる）。

• 1は、aは末尾が00の状態で、110で終わる列はaに来ない。
• 2は、bは末尾が01の状態である。
• 4は、dは末尾が11の状態で、110の最後の0を読む前の段階にあたる。

根拠：有限オートマトンの状態遷移表の読み方