オートマトンとは
オートマトン（おーとまとん）とは、あらかじめ決められた「状態」を持ち、外部から「入力（何らかのアクション）」を受けると、そのルールに従って「次の状態」へと遷移（変化）していく、自動的に動作する仕組みや概念モデルのことです。日本語では「自動機械」とも呼ばれます。複雑なコンピュータのプログラムやハードウェアをそのまま設計すると混乱しやすいため、「今どの状態で、何が起きたらどうなるか」というシンプルな状態の移り変わりとしてモデル化して整理するために使われます。身近なところでは、自動販売機のコイン受付処理や、駅の自動改札機、プログラミング言語の文法チェックなどでこのオートマトンの考え方が活用されています。
具体例
駅の「自動改札機」の動作をオートマトン（状態遷移）で表してみます。
1. 初期状態：【閉（ロック）】
2. 入力：切符を通す、またはICカードをタッチする
3. 状態変化：ロックが解除され、【開（通過可能）】状態へ移行
4. 入力：人が改札を通過する
5. 状態変化：扉が閉まり、再び【閉（ロック）】状態に戻るこのように、「現在の状態」と「入力」の組み合わせによって「次にどう動くか」を厳格に定義する仕組みがオートマトンです。
もう少し詳しく
オートマトンの代表的なモデルである「有限オートマトン」は、有限個の「状態」と、状態間を移動するための「遷移規則」、そして文字列を読み込み終わったときに処理が成功したかどうかを判定する「受理状態（最終状態）」から構成されます。状態の遷移を図解した「状態遷移図」では、状態を円（○）で、遷移を矢印（→）で表し、受理状態は二重丸（◎）で描かれるのが一般的です。プログラムの内部では、正規表現にマッチするかどうかの判定や、コンパイラ（人間が書いたコードを機械語に翻訳するプログラム）がプログラムの文字列（ソースコード）を単語レベルに切り分ける「字句解析」の処理において、有限オートマトンのアルゴリズムが直接的に利用されています。これにより、複雑な条件分岐のコードを書かなくても、表や図に基づいたシンプルなルールで文字列の正当性を高速にチェックできます。
試験でのポイント
基本情報技術者試験では、状態遷移図（○と矢印の図）や状態遷移表が提示され、「特定の文字列（例えば『0101』など）を入力した結果、最終的にどの状態に行き着くか」、あるいは「受理状態（二重丸）に到達する入力文字列はどれか」といった、図を正確に読み解いてシミュレーションするトレース問題が頻出します。落ち着いて現在の状態から入力文字を一文字ずつ追いかければ必ず解ける問題ですので、得点源にしましょう。また、現在の状態と入力だけで次の状態が一意に決まる「決定性有限オートマトン」と、複数の遷移先があり得る「非決定性有限オートマトン」という用語の違いについても、概要レベルで問われることがあります。
関連する用語
オートマトンの動作を視覚的に表現した状態遷移図、文字列のパターンマッチングに用いられオートマトンと等価な表現能力を持つ正規表現、プログラムの翻訳過程の初期段階である字句解析などが関連します。