問題プレビューID: 5ee95748応用情報技術者試験 2009年(平成21年度)春期 午前

問 3
応用情報技術者試験 2009年(平成21年度)春期 午前

次に示す有限オートマトンが受理する入力列はどれか。ここで,S₁ は初期状態を,S₃ は受理状態を表している。

解説

正解は「ウ」です。

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

  • S₁:1 で S₂ へ,0 で S₃ へ
  • S₂:1 で S₁ へ,0 で S₂ に留まる
  • S₃:1 で S₃ に留まる(受理状態),0 で S₂ へ

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

  • ア 1011:S₁→(1)S₂→(0)S₂→(1)S₁→(1)S₂。S₂ で終了し受理されません。
  • イ 1100:S₁→(1)S₂→(1)S₁→(0)S₃→(0)S₂。S₂ で終了し受理されません。
  • ウ 1101:S₁→(1)S₂→(1)S₁→(0)S₃→(1)S₃。S₃ で終了し受理されます。
  • エ 1110:S₁→(1)S₂→(1)S₁→(1)S₂→(0)S₂。S₂ で終了し受理されません。

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

関連問題

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