オートマトン（automaton）とは、数学の概念の一つで、抽象的な機械を用いて「入力を受け入れるか（受理）、拒否するか」を判定する仕組みを表したものです。しばしばステートマシン（状態機械）とも呼ばれます。現実の装置を正確に再現するというより、情報処理の本質を単純化して捉えるためのモデルです。

入力と受理・拒否の考え方

オートマトンには入力（記号の列）が左から順に与えられ、機械は一度に1つの記号を読み取り（数学者はこれをシンボルと呼びます）、そのたびに内部の状態が規則に従って変化します。すべての記号を読み終えたときに機械が最終的な状態（受理状態）にいれば「受理」、そうでなければ「拒否」となります。

直感的には、自動販売機に似ています。商品を買うとき、機械にコイン（またはお金）を入れるたびに内部の状態が遷移します。正しい金額に到達した状態が受理状態で、商品が出ます。間違ったコインや不足している場合は、受理状態に至らず拒否されます。

オートマトンの基本構成

  • 入力アルファベット: 読み取り可能な記号の集合（例: {0,1}）
  • 状態の集合: 機械が取りうる内部の構え（例: S0, S1）
  • 遷移規則: 現在状態と入力記号に応じて次の状態を定める規則
  • 開始状態: 計算を始めるときにいる状態
  • 受理状態（最終状態）: 入力を読み終えたときにここにいれば受理

多くの入門書では、これを「(状態集合, アルファベット, 遷移, 開始状態, 受理状態集合)」の形でまとめます。式を覚えるより、上の5点がそろえば一つのオートマトンが定義できる、と理解しましょう。

有限状態機械（FSM）と有限状態図

機械が数えられる有限の数の状態しか持たないとき、これを有限状態機械と呼びます。有限状態機械のすべての状態と遷移を丸と矢印で描いた図が有限状態図（状態遷移図）です。矢印のラベルが「どの記号を読んだときにどこへ進むか」を表します。二重丸は受理状態、矢印のない外部から入る矢印は開始状態を示すのが一般的な記法です。

決定性と非決定性

  • 決定性有限オートマトン（DFA）: 各状態・各記号に対して次に進む先がただ一つだけ決まる。
  • 非決定性有限オートマトン（NFA）: 同じ状態・同じ記号で複数の候補に分岐できたり、記号を消費せずに移動するε遷移を持てる。

理論的には、NFAで認識できる言語はDFAでも認識できます（subset constructionと呼ばれる方法でDFAに変換可能）。また、等価なDFAは冗長な状態をまとめて最小化できます。

簡単な例

「1の個数が偶数のときに受理する」オートマトン（アルファベット {0,1}）:

  • 状態: S_even（受理）, S_odd（非受理）
  • 開始状態: S_even
  • 遷移: 0 を読むと状態は変わらない。1 を読むと S_even ↔ S_odd を切り替える。

どれだけ長い入力でも、必要なのは「奇数か偶数か」という2状態だけです。これは「有限の記憶で判定できる典型例」です。

できること・できないこと

  • できること: 単純なパターンの検出、特定の接頭辞/接尾辞/部分文字列の有無判定、文字種や区切りのルールに基づく分類など。正規表現で表せるパターンは有限状態機械で実現できます。
  • 苦手なこと: 任意に大きい数を正確に数える、対応する括弧の完全一致、a^n b^n のように「数を比べる」問題、回文判定など。これらにはスタックを持つプッシュダウン・オートマトンや、より強力なチューリングマシンといった別の抽象機械が必要になります。

主な応用

  • プログラミング言語処理: 字句解析器（トークナイザ）は正規表現から生成した有限状態機械で実装されます。
  • 通信・プロトコル: 状態とイベントに基づく接続の管理やエラー処理。
  • UI/ゲームの挙動: 画面遷移、キャラクターAI、ボタンの押下状態管理。
  • ハードウェア設計: 制御回路の状態遷移記述（同期回路の制御部）。
  • テキスト検索・検疫: パターンマッチング、高速フィルタ。

設計と解析の手順（実務の勘所）

  • どんな入力記号を扱うか（アルファベット）を決める。
  • 判定に必要な「覚えておくべき事実」だけを状態として抽出する。
  • 各状態で各記号を読んだときの遷移を漏れなく定義する。
  • 開始状態と受理状態を明確にする。テスト用の入力例で挙動を確認する。
  • 複雑ならまずNFAで考え、必要ならDFAに変換して最小化する。

用語の整理

  • シンボル: アルファベットから取られる最小単位の記号。
  • 文字列: シンボルを並べた列（空文字列も含む）。
  • 言語: 文字列の集合（どの文字列を受理するかの全体）。
  • 受理（受け入れ）/拒否: 入力を読み終えたときの状態に基づく判定。
  • 有限状態図: 状態と遷移を図示したもの。挙動の把握とデバッグに有効。

まとめると、オートマトンは「入力を一つずつ読みながら状態を更新し、最後に受理か拒否かを答える」抽象的な機械です。とりわけ状態数が有限のものが有限状態機械であり、正規表現と等価な表現力をもち、実装・解析・最適化の手法（NFA→DFA、最小化など）も確立しています。まずは身近な自動販売機の例や、簡単なパターン判定から考え始めると理解が進みます。