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

解説

正解は3です。 有限オートマトンの状態遷移表から、110で終わるビット列を読み終えたときの状態を求める問題です。 表を見ると、aとcは同じ遷移（0ならa、1ならb）をし、bとdも同じ遷移（0ならc、1ならd）をします。 このため、読み終えた時点の状態は直前に読んだ2ビットだけで決まります。 【状態の意味】 直前のビットが0で、最後のビットが0なら、状態はaです。 直前のビットが0で、最後のビットが1なら、状態はbです。 直前のビットが1で、最後のビットが0なら、状態はcです。 直前のビットが1で、最後のビットが1なら、状態はdです。 たとえばaから110を読むと、1でb、次の1でd、最後の0でcに達します。 どの状態から始めても、末尾が「10」で終わる列は必ずcに達します。 【選択肢別解説】 1：× 状態aに達するのは、末尾2ビットが00の列です。 110で終わる列はaに達しないため、aを受理状態にしても受理できません。 2：× 状態bに達するのは、末尾2ビットが01の列です。 末尾が0である110の列はbに達しないため、受理できません。 3：○ 110で終わる列は末尾2ビットが10なので、どの状態から読み始めても必ずcに達します。 したがって、cを受理状態にすれば110で終わる列をすべて受理できます。 4：× 状態dに達するのは、末尾2ビットが11の列です。 110の列は最後が0なのでdには達せず、受理できません。 【ポイント】 状態遷移表で同じ行の内容を持つ状態があるときは、各状態が「直前の入力の何を覚えているか」を考えると整理できます。 この表のcは「末尾が10」を覚えている状態なので、厳密には…010で終わる列も受理します。