問題プレビューID: 4ee0d48c基本情報技術者試験 午前免除試験 2016年6月12日

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

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

解説

正解は「ウ」です。

図の有限オートマトンの遷移は次のとおりです。初期状態を S,受理状態(二重丸)を D とします。

  • S:1 で A へ,0 で C へ
  • A:1 で B へ,0 で S へ
  • B:1 で D へ,0 で S へ
  • C:0 で C に留まる(それ以外の遷移はなく,受理状態には到達しない)
  • D(受理状態):1 で E へ,0 で S へ
  • E:0 でも 1 でも E に留まる

各入力列を初期状態 S からたどります。

  • ア 01011:S→(0)C となり,続く 1 の遷移がないため受理されません。
  • イ 01111:S→(0)C となり,同様に受理されません。
  • ウ 10111:S→(1)A→(0)S→(1)A→(1)B→(1)D。受理状態 D で終了するので受理されます。
  • エ 11110:S→(1)A→(1)B→(1)D→(1)E→(0)E。受理状態でない E で終了するので受理されません。

したがって,正解は「ウ」です。

関連問題

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