オートマトンとは？おーとまとん
オートマトンとは、状態と、入力に応じてどの状態へ移るかを定めた遷移規則の集合で表す計算モデル。状態が有限個の有限オートマトンが代表で、状態遷移図や状態遷移表で書き表す。入力の並びが規則に合うかを判定する型のほか、遷移のたびに出力を返す型もある。文字の並びのパターンを記号で表す正規表現と同じ範囲の文字列を判定でき、字句解析や文字列検索の実装の土台になる。
最終更新：2026-10-09
この語が出る過去問を解く →背景
「この文字列は規則に合っているか」を人が場合分けで確かめると漏れが出る。状態と遷移だけに落とせば、判定は表を引く単純作業になり、そのまま機械に任せられる。形式言語（正規表現や、括弧の対応のような入れ子の並びまで書ける、より表現力の高い文脈自由文法）と対にして、どの記法がどこまでを表せるかという階層で理解させるのが出題の狙いである。
具体例
自動販売機は「硬貨投入待ち→商品選択可→排出中」といった状態を持ち、投入・選択・返却という入力で状態が移る。この動きは状態遷移図でそのまま書け、同じ書き方が通信プロトコルや画面遷移の設計にも使われる。
試験での引っ掛け
有限オートマトンが判定できるのは正規表現で書ける範囲まで。括弧の対応のように「いくつ開いたか」を数え続ける必要がある並びは判定できない。状態遷移図と状態遷移表は同じ内容の別表記で、どちらから読み取らせる出題もある。
関連用語
出た過去問
出典：平成28年度 春期 基本情報技術者試験 午前 問2（IPA）
次の状態遷移図で表現されるオートマトンで受理されるビット列はどれか。ここで，ビット列は左から順に読み込まれるものとする。
正解：1010
要点：受理列は0*1+0に続く任意列。1の後の0が鍵
この状態遷移図は、初期状態で0を読み飛ばし、1が現れると次の状態へ移り、そこで1が続く限りとどまり、0を読んだ時点で受理状態に入って以降は何が来ても受理状態のままという構造になっている。つまり受理される列は「0が0個以上→1が1個以上→0→任意の列」という形である。この形にあてはまるのは1010で、1で第2状態へ移り、続く0で受理状態に達し、残りの10はそのまま受理状態を回る。
出典：平成30年度 春期 基本情報技術者試験 午前 問4（IPA）
入力記号、出力記号の集合が{0, 1}であり、状態遷移図で示されるオートマトンがある。0011001110を入力記号とした場合の出力記号はどれか。ここで、S1は…
正解：0001000110
要点：オートマトンは入力を1文字ずつ追い、辺の出力側を順に並べる
状態遷移図に従って入力を1文字ずつ処理し、遷移のラベルの出力側を並べればよい。初期状態S1から 0,0 は自己ループで出力0が2個。次の1でS1→S2（出力0）、続く1でS2→S3（出力1）。次の0でS3→S1（出力0）、0で自己ループ（出力0）、1でS1→S2（出力0）、1でS2→S3（出力1）、1はS3の自己ループ（出力1）、最後の0でS3→S1（出力0）。並べると 0001000110 となる。
出典：令和4年度 公開問題 基本情報技術者試験 科目A 問4（IPA）
入力記号、出力記号の集合が{0, 1}であり、状態遷移図で示されるオートマトンがある。0011001110を入力記号とした場合の出力記号はどれか。ここで、入力記…
正解：0001000110
要点：オートマトンは初期状態から遷移を順にたどり出力を並べる
初期状態から入力を1文字ずつ読み、遷移のラベルに従って出力を並べる。出力が1になるのは、1が2つ以上続いて第3の状態へ入った後だけで、それ以外の遷移はすべて0を出力する。入力を順にたどると、2組目の1の位置と、その後に1が3つ続く箇所の2文字目以降で1が現れ、出力は0001000110となる。
出典・参考
公式シラバスの1 基礎理論 ＞ 3. 情報に関する理論 ＞ (9) コンパイラ理論に掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。