問題プレビューID: 77d9f78e基本情報技術者試験 午前免除試験 2018年12月9日

問 3
基本情報技術者試験 午前免除試験 2018年12月9日

表は,入力記号の集合が {0,1}\{0, 1\},状態集合が {a,b,c,d}\{a, b, c, d\} である有限オートマトンの状態遷移表である。長さ 3 以上の任意のビット列を左(上位ビット)から順に読み込んで最後が 110 で終わっているものを受理するには,どの状態を受理状態とすればよいか。

状態01
aab
bcd
cab
dcd
解説

正解は「ウ」です。

この状態遷移表では,各状態は直前に読み込んだ 2 ビットの並びを表しています。

  • 状態 a は「00」を表す。
  • 状態 b は「01」を表す。
  • 状態 c は「10」を表す。
  • 状態 d は「11」を表す。

例えば,初期状態を a として 1,1,0 の順に読み込むと,a →(1)→ b →(1)→ d →(0)→ c と遷移し,最後は状態 c になります。ビット列が 110 で終わるとき,末尾の 2 ビットは常に「10」であり,読み終えた直後の状態は c になります。したがって,c を受理状態とすればよいので,「ウ」が正解です。

  • ア: 状態 a は末尾 2 ビットが「00」の場合の状態です。
  • イ: 状態 b は末尾 2 ビットが「01」の場合の状態です。
  • エ: 状態 d は末尾 2 ビットが「11」の場合の状態です。

関連問題

本文が同じ・似ている問題を表示しています