平成26年度 春期 午前 問4

✓ これが正解ウc

解説

末尾の 110 を読み進めた先にいる状態を選びます。

設問は、末尾が 110 で終わるビット列を受理させるために、どの状態を受理状態にすればよいかを選ばせています。有限オートマトンの問題ですが、出発点を決める必要はありません。まず 1 を読むと、a からは b へ、b からは d へ、c からは b へ、d からは d へ動きますから、行き先は b と d の二つに絞られます。続けてもう一度 1 を読むと、b も d もどちらも d へ移り、ここで出発点の違いが消えてしまいます。最後に 0 を読むと d は c へ移ります。末尾の三ビットを読み終えた列は、どこから始まっていても c にいることになります。状態遷移表を逆から読むと、この四つの状態が直前の二ビットを覚えていることも分かります。a は 00、b は 01、c は 10、d は 11 にあたり、110 を読み終えた時点で直前の二ビットは 10 ですから、やはり c です。なお設問が求めているのは取りこぼさないことなので、末尾が 10 の列も一緒に受理されることは差し支えありません。

ほかの選択肢はなぜ違うのか

• アa：直前の二ビットが 00 のときにいる状態です。末尾が 110 の列を読み終えた時点でここに戻ってくることはなく、取りこぼしが生じます。
• イb：直前の二ビットが 01 で終わる列の行き先です。求める列は最後に 0 を読んで移るので、その到着先とは別の状態になります。
• エd：1 を二つ読んだところで止めた形で、直前の二ビットが 11 の状態にあたります。最後の 0 を読むと、そこからさらに別の状態へ移ります。