問題プレビューID: 0a77bb4c基本情報技術者試験 午前免除試験 2025年1月26日

問 3
基本情報技術者試験 午前免除試験 2025年1月26日

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

状態01
aab
bcd
cab
dcd
解説

正解は「ウ」です。

与えられた状態遷移表を調べると,状態 a と c は同じ遷移(0 で a,1 で b),状態 b と d も同じ遷移(0 で c,1 で d)をしており,このオートマトンは実質的に直前の 2 ビットの並びだけを記憶しています。

  • 直前の 2 ビットが「00」のとき状態 a
  • 直前の 2 ビットが「01」のとき状態 b
  • 直前の 2 ビットが「10」のとき状態 c
  • 直前の 2 ビットが「11」のとき状態 d

ビット列を左から順に読み込むので,初期状態 a から「110」を読み込むと,a →(1)→ b →(1)→ d →(0)→ c となり,状態 c になります。したがって,最後が 110 で終わるビット列を受理するには,状態 c を受理状態とすればよいことになります。

  • ア・イ・エ: a,b,d を受理状態とした場合は,110 で終わるビット列を受理できません。

関連問題

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