修了試験 2026-01-25実施分 基本情報技術者試験 問3

解説

正解は3です。 この問題は、状態遷移表から、各状態が何を表しているかを見抜く問題です。 表では、aとcはどちらも、0を読むとa、1を読むとbへ遷移します。 bとdはどちらも、0を読むとc、1を読むとdへ遷移します。 このため、到達する状態は、最後に読んだ2ビットだけで決まります。 末尾が00ならa、01ならb、10ならc、11ならdです。 どの状態からでも、1を2回続けて読むと必ずdになります。 dで0を読むとcへ移るので、末尾が110の列は必ずcで終わります。 【選択肢別解説】 1：× aに到達するのは、末尾が00の列です。 末尾が110の列はaで終わらないので、aを受理状態にしても受理できません。 2：× bに到達するのは、末尾が01の列です。 最後が0で終わる110の列は、bにはなりません。 3：○ 末尾が110の列は、11を読んだ時点でdになり、最後の0でcへ移ります。 直前までの状態にかかわらず必ずcで終わるので、cを受理状態とします。 4：× dに到達するのは、末尾が11の列です。 110の列は、最後の0でdからcへ移るので、dでは終わりません。 【ポイント】 遷移先が同じ状態の組を見つけると、各状態が「直前に読んだビット」を表していると分かります。 なお、この表では末尾が010の列もcで終わります。 選択肢の中で、110で終わる列を必ず受理できる状態がcだけなので、cが正解になります。