問題プレビューID: bdd4d6c6応用情報技術者試験 2016年(平成28年度)秋期 午前

問 4
応用情報技術者試験 2016年(平成28年度)秋期 午前

表は,入力記号の集合が {0,1}\{0, 1\},状態集合が {a,b,c,d}\{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

110 で終わるビット列を読み終えたとき,直前の 2 ビットは「10」です。したがって,そのときの状態は c になるので,受理状態を c にすればよいことになります。

よって正解は「ウ」です。

関連問題

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