オートマトンとは？おーとまとん
オートマトンとは、状態の集合と、入力に応じてどの状態へ移るかを定めた遷移規則の組で計算を表す数学モデル。応用情報で中心になるのは状態が有限個の有限オートマトンで、記憶が状態数までしかないため受理できるのは正規表現で書ける範囲に限られる、という認識能力の上限が論点になる。
最終更新：2026-10-06
この語が出る過去問を解く →背景
言語の文法を人の直感で扱っている限り、ある処理系がどこまでの構造を解釈できるのかを言い切れなかった。状態と遷移という最小の部品だけで計算を定義したことで、扱える言語の範囲を階層として比較できるようになり、字句解析には有限オートマトン、構文解析にはより強いモデルという設計上の使い分けが導けるようになった。応用情報では状態遷移図・状態遷移表を読み取らせる形で出題される。
具体例
UNIX系のgrepやlex（flex）は、与えられた正規表現を有限オートマトンに変換してから入力を1文字ずつ走査する。自動販売機の「投入待ち→選択待ち→排出中」のような制御も、状態と遷移だけで記述できる典型例である。
試験での引っ掛け
有限オートマトンで何でも認識できると読ませる出題に注意する。括弧の対応のように「いくつ開いたか」を覚える必要のある文脈自由言語は有限オートマトンでは扱えず、スタックを持つプッシュダウンオートマトンが要る。状態遷移図と状態遷移表は同じ内容の別表記であって、別のモデルではない点も混同されやすい。
関連用語
出た過去問
出典：平成28年度 秋期 応用情報技術者試験 午前 問4（IPA）
表は、入力記号の集合が{0, 1}、状態集合が{a, b, c, d}である有限オートマトンの状態遷移表である。長さ3以上の任意のビット列を左（上位ビット）から…
正解：c
要点：受理状態はパターンを読み終えた直後に到達する状態
受理状態は「末尾の3ビットが110である」ことを読み終えた直後の状態です。初期状態 a から1を読むと b、続けて1を読むと d へ進み、この d が「11を読み終えた」状態にあたります。さらに0を読むと c へ遷移するので、110を読み終えた時点の状態は c です。したがって c を受理状態にすればよいことになります。
出典・参考
公式シラバスの1 基礎理論 ＞ 3. 情報に関する理論 ＞ (10) コンパイラ理論に掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。