平成21年度 高度共通 午前I（PM試験） 問2

正解：ウ

AI解説

有限オートマトンは，初期状態S₁から入力記号を1文字読むごとに状態遷移図に従って状態を移し，入力をすべて読み終えた時点で受理状態S₃にあればその入力列を受理する。各選択肢の4文字の列を図の遷移に従って1文字ずつたどると，最後にS₃に到達するのは1101だけである。 ア: 1011をたどると，読み終えたときの状態が受理状態S₃にならないため受理されない。 イ: 1100をたどると，最終状態がS₃にならないため受理されない。 ウ: 正解。1→1→0→1の順に遷移をたどると，最後に受理状態S₃で終わるため受理される。 エ: 1110をたどると，最終状態がS₃にならないため受理されない。 💡 この種の問題は全選択肢を状態遷移図の上で機械的にトレースするのが確実。途中でS₃を通過しても意味はなく，「読み終えた瞬間」に受理状態にいるかどうかだけで判定する。