問題プレビューID: 0d3dce8e基本情報技術者試験 午前免除試験 2012年12月16日

問 4
基本情報技術者試験 午前免除試験 2012年12月16日

図で表される有限オートマトンで受理される文字列はどれか。ここで,初期状態は黒い矢印で指された状態,受理状態は二重丸の状態である。

解説

正解は「ウ」です。

このオートマトンの遷移は次のとおりです。

  • S1(初期状態):0 で S4 へ,1 で S2 へ
  • S2:0 で S1 へ,1 で S3 へ
  • S3:0 で S1 へ,1 で S5 へ
  • S4:0 で S1 へ(1 の遷移はない)
  • S5(受理状態):1 で S6 へ
  • S6:0 または 1 で S7 へ
  • S7:0 または 1 で S7 に留まる

各文字列を初期状態 S1 からたどります。

  • ア 01011:S1→(0)S4。S4 には 1 の遷移がないため,途中で行き先がなく受理されません。
  • イ 01111:S1→(0)S4。同様に S4 で 1 を入力できず,受理されません。
  • ウ 10111:S1→(1)S2→(0)S1→(1)S2→(1)S3→(1)S5。受理状態 S5 で終了するので受理されます。
  • エ 11110:S1→(1)S2→(1)S3→(1)S5→(1)S6→(0)S7。S7 は受理状態ではなく,S5 に戻る経路もないため受理されません。

したがって,受理状態で終了する「ウ」が正解です。

関連問題

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