オートマトンとは？おーとまとん
オートマトンとは、状態と、状態間を移る遷移規則（入力に応じてどの状態に移るか）の集合で表現される計算モデル。有限個の状態しか持たない「有限オートマトン」が代表的で、字句解析や正規表現の処理系に応用される。
最終更新：2026-10-07
この語が出る過去問を解く →具体例
自動販売機の「硬貨投入待ち→商品選択待ち→排出中」といった状態遷移は、状態遷移図（オートマトン）で表現できる。プログラムの状態遷移設計にも同じ考え方が使われる。
試験での引っ掛け
有限オートマトンが扱えるのは正規表現に対応する範囲まで。括弧の対応のように「いくつ開いたかを覚える」必要がある言語（文脈自由文法）は有限オートマトンでは認識できず、スタックを持つプッシュダウンオートマトンが要る。状態遷移図と状態遷移表は同じ内容の別の書き方で、どちらから読み取らせる出題もある。
関連用語
出た過去問
出典：平成28年度 秋期 高度試験 午前Ⅰ 問2（IPA）
表は、入力記号の集合が{0，1}、状態集合が{a，b，c，d}である有限オートマトンの状態遷移表である。長さ3以上の任意のビット列を左（上位ビット）から順に読み…
正解：c
要点：受理状態は目的の並びを読み終えた時点の状態
初期状態aから110を読ませると、1でb、次の1でd、最後の0でcに至る。さらにcは0を読むとa、1を読むとbへ移り、末尾が110になった瞬間だけcに入る構造になっている。したがって受理状態はcとすればよい。
出典・参考
公式シラバスの1 基礎理論 ＞ 3. 情報に関する理論 ＞ (10) コンパイラ理論に掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。