必ず受かる情報処理技術者試験

当サイトは、情報処理技術者試験に合格するためのWebサイトです。
ITパスポート試験，基本情報技術者,応用情報技術者,高度試験の過去問題と解答及び詳細な解説を掲載しています。
  1. トップページ
  2. 高度共通　午前1
  3. 平成26年度春季問題一覧
  4. 平成26年度春季問題2-解答・解説-分析

平成26年度春季問題

問題2

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

ア a
イ b
ウ c
エ d

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

ア a
イ b
ウ c
エ d

解答：ウ

＜解説＞

  1. 110の左端の1を読み込む：状態がa又はcの時はb、bまたはdの時はdに遷移する
  2. 110の中央の1を読み込む：状態がb又はdの時に1を読み込むとdに遷移する
  3. 110の右端の0を読み込む：状態がdの時に0を読み込むとcに遷移する

したがって、ウが正解である。