対象試験と出題頻度
オートマトン（有限オートマトン）は、応用情報技術者で出題されるテーマです。
状態遷移図を読み取って「受理される入力列」を選ぶ問題や、状態遷移表から「受理状態」を特定する問題が定番化しており、図を正確にたどる力が問われます。
詳細をクリックして確認
応用情報技術者
★★☆☆☆
ランクC（応用）余裕があれば覚える
用語の定義
情報処理試験を勉強していると、「オートマトンって何？状態遷移図をどう読めばいいの？」と手が止まりがちです。
オートマトン（Automaton）とは、一言で言うと
「入力記号を1つずつ読み取り、あらかじめ決められたルールに従って状態を切り替えながら、最終的にその入力列を受理するか拒否するかを判定する数学的モデル」
のことです。
イメージとしては、「自動改札機」です。
改札機は「切符を入れる」「ICカードをタッチする」といった入力に応じて、
内部の状態が「待機中→認証中→通過許可」と切り替わります。
最終的にゲートが開けば「受理」、閉じたままなら「拒否」です。オートマトンも同じ考え方で、入力に応じて状態を遷移させ、最後に受理状態にいるかどうかで判定します。
📊 オートマトンの基本情報
| 項目 | 内容 |
|---|---|
| 英語名 | Automaton（複数形：Automata） |
| 試験で出る範囲 | 有限オートマトン（Finite Automaton）のみ |
| 最大の特徴 | 状態遷移図（または状態遷移表）で表現される |
| 構成要素 | 状態の集合、入力記号の集合、遷移関数、初期状態、受理状態 |
解説
コンピュータが文字列やデータを処理するとき、「この入力は受け入れてよいか」を判定する場面が数多くあります。たとえば正規表現によるパターンマッチや、コンパイラが文法チェックを行う字句解析です。
こうした「入力列の判定」を形式的に記述するために生まれたのがオートマトンという計算モデルです。
IPA試験で問われるのは、最も基本的な「有限オートマトン」です。
有限オートマトンの5つの構成要素
有限オートマトンは次の5つで定義されます。
| 構成要素 | 意味 | 自動改札の例え |
|---|---|---|
| 状態の集合 | オートマトンが取りうる全状態 | 待機中・認証中・通過許可・エラー |
| 入力記号の集合 | 受け取りうる入力の種類 | 切符・ICカード・何もなし |
| 遷移関数 | 「今の状態＋入力」→「次の状態」のルール | 待機中＋ICタッチ→認証中 |
| 初期状態 | 処理開始時の状態（1つだけ） | 待機中 |
| 受理状態 | 入力を全部読み終わったとき、この状態にいれば「受理」 | 通過許可（ゲートが開く） |
状態遷移図の読み方
状態遷移図では、丸（○）が状態、矢印が遷移、矢印に付いたラベルが入力記号を表します。
二重丸（◎）が受理状態、外からの矢印が初期状態です。
▼ 状態遷移図の読み方（HTMLイメージ）
─ 1 →
（非受理）
（受理状態 ◎）
※ 上図は簡略化した例です。実際の試験問題では各状態からすべての入力記号に対する遷移が矢印で記載されます。
▶ DFA（決定性）とNFA（非決定性）の違い（クリックで展開）
有限オートマトンには「決定性（DFA）」と「非決定性（NFA）」の2種類があります。
| 種類 | 特徴 | 遷移先 |
|---|---|---|
| DFA （決定性有限オートマトン） |
ある状態である入力記号を読んだとき、遷移先が必ず1つに決まる | 常に1つ |
| NFA （非決定性有限オートマトン） |
遷移先が複数存在したり、入力なしで遷移（ε遷移）したりする場合がある | 0個以上 |
理論上、DFAとNFAの認識能力は等価です。
つまり、NFAで受理できる言語は必ずDFAでも受理できます。
IPA試験ではDFAの問題がほとんどなので、NFAとの違いは「遷移先が1つか複数か」とだけ押さえておけば十分です。
状態遷移図の追い方（具体例）
ここだけは確実に押さえてください。試験では「初期状態から入力列の文字を1つずつ読み、遷移先をたどって最後に受理状態にいるかどうか」を確認するだけで正答できます。
▼ 追跡例：入力列「1101」を判定する
状態S1が初期状態、S3が受理状態のオートマトンで以下のように追跡します（AP H21春 午前問3の題材）。
| 手順 | 入力 | 現在の状態 → 次の状態 |
|---|---|---|
| 1 | 1 | S1 → S2 |
| 2 | 1 | S2 → S1 |
| 3 | 0 | S1 → S3 |
| 4 | 1 | S3 → S3（受理状態） |
最終状態がS3（受理状態）なので、入力列「1101」は受理されます。
では、この用語が試験でどのように出題されるか見ていきましょう。
💡 オートマトンの核心を3行で
・入力記号を1つずつ読み、ルールに従って状態を遷移させ、最後に受理状態にいれば「受理」
・状態遷移図では、丸が状態、矢印が遷移、二重丸が受理状態を表す
・試験では「入力列を初期状態から1文字ずつたどる」だけで正答できる
試験ではこう出る！
オートマトンは、応用情報技術者の午前問題で数年に1回のペースで出題されています。
出題パターンは大きく2つに分かれます。
📊 過去問での出題実績
| 試験回 | 出題内容 | 問われたポイント |
|---|---|---|
| AP H28秋 午前 問4 |
状態遷移表から「110で終わるビット列」を受理する状態を特定する問題。 | ・遷移表を図に変換し、末尾「110」の遷移先を追跡できるか ・H26春AP問4、H17春SW問7でも同一問題が出題 |
| AP H25春 午前 問3 |
偶数個の1を含むビット列を受理する状態遷移図の穴埋め問題。 | ・遷移図のa, bに入る入力記号を論理的に特定できるか ・H17春FE問11でも同一問題が出題（流用問題） |
| AP H21春 午前 問3 |
状態遷移図を見て、受理される入力列を4択から選ぶ問題。 | ・4つの入力列をそれぞれ初期状態からたどり、受理状態に到達するものを判別 |
📝 IPA試験での出題パターン
パターン1：「受理される入力列を選べ」
状態遷移図が与えられ、4つの入力列（ビット列）の中から受理されるものを選ぶ形式。初期状態から1文字ずつたどり、最終状態が二重丸（受理状態）になるかを確認すれば解ける。焦って途中で遷移先を見間違えるのがひっかけポイント。
パターン2：「受理状態（または遷移の穴埋め）を答えよ」
状態遷移表や状態遷移図の一部が空欄になっており、「特定のパターンのビット列を受理するにはどの状態が受理状態か」「空欄に入る入力記号は何か」を問う形式。遷移表を状態遷移図に書き直してから追跡すると解きやすい。
試験ではここまででOKです。NFAからDFAへの変換アルゴリズムや、チューリングマシンとの関係まで問われることはないので深追いは不要です。
【確認テスト】理解度チェック
ここまでの内容を理解できたか、簡単なクイズで確認してみましょう。
Q. 有限オートマトンの説明として、最も適切なものはどれでしょうか？
- A. 演算子を被演算子の後ろに記述し、スタックを用いて括弧なしで数式を計算する表記法である。
- B. プログラムの構文規則を再帰的な生成規則の集合として形式的に定義する記法である。
- C. 有限個の状態と遷移規則を持ち、入力記号列を1つずつ読み取りながら状態を遷移させ、受理するかどうかを判定する数学的モデルである。
正解と解説を見る
正解：C
解説：
有限オートマトンは、有限個の状態・入力記号の集合・遷移関数・初期状態・受理状態の5要素で構成され、入力記号列に対して受理・拒否を判定する計算モデルです。
選択肢Aは逆ポーランド記法（後置記法）の説明です。数式の表記方法であり、状態遷移や受理判定の概念は含まれません。選択肢BはBNF（バッカス・ナウア記法）の説明です。プログラミング言語の構文規則を定義するための記法であり、入力列の受理判定を行うモデルではありません。
よくある質問（FAQ）
Q. オートマトンと正規表現はどう関係していますか？
有限オートマトンが受理できる言語の集合と、正規表現で表現できる言語の集合は完全に一致します。つまり、ある正規表現に対して必ず等価な有限オートマトンを構成でき、その逆も成り立ちます。コンパイラの字句解析では、正規表現で定義したパターンを内部的に有限オートマトンに変換して文字列マッチングを行っています。
Q. 試験で状態遷移表が出た場合、図に書き直すべきですか？
書き直すことを強く推奨します。遷移表は情報が正確ですが、人間が追跡するには視覚的に追いにくいのが難点です。余白に丸と矢印で簡単な遷移図を描くだけで、入力列のたどりやすさが大幅に向上します。AP H28秋 午前問4のような遷移表の問題は、図に変換した受験者のほうが正答率が高い傾向にあります。
Q. 有限オートマトンとチューリングマシンの違いは何ですか？
最大の違いは「記憶能力」です。有限オートマトンは有限個の状態しか持てず、外部メモリを使えません。一方チューリングマシンは無限長のテープ（メモリ）を持ち、読み書きと移動が自由にできるため、有限オートマトンでは判定できない言語も扱えます。IPA試験（応用情報レベル）ではチューリングマシンの詳細は問われないので、「有限オートマトンより計算能力が上位のモデル」とだけ認識しておけば十分です。
