平成28年度 秋期 午前 問4

✓ これが正解ウc

解説

末尾の110を後ろから3手だけ追えば決まります。

状態遷移表は、行がいまの状態、列が読んだ記号、交点が移った先の状態を表します。この問は受理状態を一つ選ぶ形なので、受理させたいビット列を末尾から3手だけ追うのが速い解き方です。まず110の先頭にある1を読む動きを見ると、a は b へ、b は d へ、c は b へ、d は d へ移ります。移った先は b か d の二つだけです。続けてもう一度1を読むと、b も d もそろって d へ移るので、ここで状態は d 一つに定まります。最後に0を読むと d は c へ移ります。つまり、どこから読み始めたとしても、末尾が110であるビット列を読み終えた時点では必ず c に居ます。逆向きも確かめます。c へ入るのは、0の列が c になっている行、すなわち b と d から0を読んだときだけで、その b と d へ入るのはどちらも1を読んだときです。つまり c に居るのは、末尾が10で終わっているときです。010のように、末尾は10でも110ではない列も c に着きますが、110で終わる列は必ず c に着き、残る三つの状態はどれも110で終わった列を受け取れませんから、受理状態に選べるのは c だけです。長さ3以上という断りは、この3手ぶんを必ず読めるという保証です。

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

• アa：a に留まるのは0を読み続けている間だけで、1を読んだ時点でここから離れます。受理させたい列の末尾は0ですが、その一つ前が1である以上、読み終わりにこの状態へ戻ってくることはありません。
• イb：ここへ入るのは、直前に1を読んだ場合だけです。したがってこの状態が言い表しているのは、末尾が1で終わるという条件であり、追うべき3手のうち最初の1手を読んだところで手を止めた形になります。
• エd：ここへ入るには1が2回続く必要があり、言い表している条件は末尾が11で終わることです。読むべき3手のうち最後の0を数え落とすと、ちょうどこの状態にたどり着いたまま答えてしまいます。