修了試験 2018-12-09実施分 基本情報技術者試験 問3

解説

正解は3です。 状態遷移表を読み、ビット列を読み終えたときにどの状態にいるかを考える問題です。 表では、aとcはどちらも入力0でa、入力1でbに移ります。 bとdはどちらも入力0でc、入力1でdに移ります。 つまり、次の状態は「直前の状態がaかcか、bかdか」と入力ビットだけで決まります。 【状態の読み取り】 入力1を読むと、直前がaかcならb、bかdならdに移ります。 入力0を読むと、直前がaかcならa、bかdならcに移ります。 これを2回分たどると、末尾2ビットが00ならa、01ならb、10ならc、11ならdにいることが分かります。 110で終わる列は、「11」まで読んだ時点で必ずdにいて、最後の0でcに移ります。 例えばaから「110」を読むと、1でb、次の1でd、最後の0でcとたどります。 【選択肢別解説】 1：× aに着くのは末尾2ビットが00の列です。 110で終わる列は最後にcへ着くので、aを受理状態にしても受理できません。 2：× bに着くのは末尾2ビットが01の列で、最後のビットは1です。 0で終わる「110」の列はbには着きません。 3：○ 110で終わる列は、どの状態から読み始めても最後に必ずcに着きます。 cを受理状態にすれば、110で終わる列を受理できます。 4：× dに着くのは末尾2ビットが11の列です。 「11」まで読んだ時点ではdにいますが、最後の0でcに移るため、dでは受理できません。 【ポイント】 遷移先が同じ行どうしは同じ働きをする状態とみなし、状態を「末尾のビット列」に読み替えると速く解けます。 なお、この表では…010で終わる列もcに着きます。 選択肢の中で、110で終わる列を必ず受理できる状態はcだけ、という考え方で答えを選びます。