オートマトン

オートマトンとは、現在の「状態」と「入力」によって、次の「状態」が自動で決まる仕組みを数理的にモデル化したものです。

基本情報技術者試験では、主に有限オートマトン（状態の数が有限のもの）が出題されます。文字列やビット列（0と1の並び）が特定のルールに合っているかを判定する問題が定番です。

オートマトンは、身近な例でいうと「自動販売機」のような動きをします。以下の3つの要素で構成されています。
  • 状態（ステート）：現在のシステムがどういう変化の途中にあるかを表します。
  • 入力：外から与えられる信号やデータ（ボタンを押す、1が入力されるなど）です。
  • 遷移（せんい）：入力によって、ある状態から別の状態へ移り変わることです。

試験で出題される「状態遷移図」の読み方

以下は基本情報技術者試験平成30年度春午前第4問の過去問です。

（正解はア。参照：https://www.ipa.go.jp/shiken/mondai-kaiotu/gmcbt8000000fabr-att/2018h30h_fe_am_qs.pdf、https://www.ipa.go.jp/shiken/mondai-kaiotu/2018h30.html#haru_fe

以下は基本情報技術者平成18年秋期 午前 問11と基本情報技術者平成15年秋期 午前 間10で出題されたオートマトンの出題例です。

（正解はウ。参考：https://www.fe-siken.com/kakomon/15_aki/q10.html）

 

  • 〇（単一の丸）：通常の状態を表します。
  • 矢印（→）：状態が移る方向を表します。矢印の横にある数字や文字が「入力」です。
  • 太い矢印（⇒）：スタート地点（初期状態）を指し示します。
  • ◎（二重丸）：ゴール地点（受理状態 / 最終状態）を表します。
前次