修了試験 2025-01-26実施分 基本情報技術者試験 問3
表は，入力記号の集合が{0，1}，状態集合が{a，b，c，d}である有限オートマトンの状態遷移表である。 長さ3以上の任意のビット列を左（上位ビット）から順に読み込んで最後が110で終わっているものを受理するには，どの状態を受理状態とすればよいか。 表：状態遷移表 ／0｜1 a／a｜b b／c｜d c／a｜b d／c｜d
正答3
解説
正解はウ。 この状態遷移表ではaとc，bとdがそれぞれ同じ遷移をするため，読み終えた時点の状態は直前2ビットだけで決まる（a＝…00，b＝…01，c＝…10，d＝…11）。 110で終わる列は必ずcに達する（例: a→b(1)→d(1)→c(0)）。 一方，a・b・dに達する列は末尾2ビットがそれぞれ00・01・11なので110では終わり得ない。 したがって受理状態にできるのはcだけである。まとめて解く
修了試験 2025-01-26実施分を通しで解く（60問）→