平成21年度 春期 午前 問3

✓ これが正解ウ1101

解説

入力を追って最後が受理状態に落ち着くものを選びます。

有限オートマトンの受理は、初期状態から入力を 1 文字ずつ読み進め、最後の状態が受理側になっているかどうかで決まります。今回の遷移では、S₁ で 1 を読むと S₂、S₂ で 1 を読むと S₁、S₁ で 0 を読むと S₃、S₃ で 1 を読むと S₃ にとどまる、S₂ で 0 を読むと S₂ にとどまる、S₃ で 0 を読むと S₂ に落ちる、といった動きが並んでいます。判定の道は決まっていて、候補の入力を左から順に当てはめ、途中で受理でない状態に落ちて戻れなくなっていないか、末尾の状態が二重丸の側になっているかを追うだけです。1101 を当てはめると、S₁ から出発して S₂、S₁、S₃、S₃ と進み、末尾の状態が受理側にとどまります。この並びだけが最後の状態を二重丸に置いて終わるので、受理される入力に当たります。

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

• ア1011：1011 を読ませると、S₁ から S₂ に進んだ後、S₂ の自己ループを経て S₁ に戻り、最後に S₂ に落ち着きます。末尾が受理でない状態のため、この入力は受理されません。
• イ1100：1100 を読ませると、S₁ から S₂、S₁、S₃ と進んだ後、S₃ から 0 を読んで S₂ へ抜けます。最後の状態が受理側から外れており、この入力は受け入れられません。
• エ1110：1110 を読ませると、S₁ と S₂ を行き来したのち、最後の 0 で S₂ にとどまって終わります。末尾が受理でない状態で終わるため、この入力は受理されません。