修了試験 2018-12-09実施分 基本情報技術者試験 問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だけである。まとめて解く
修了試験 2018-12-09実施分を通しで解く（80問）→