オートマトン とは？

計算を数学的に表して、何を判定できるかを考えるためのモデルだよ。自動販売機のお金やボタンに応じた動きを、状態とその変化で表すイメージ。有限オートマトンでは、有限個の状態と入力記号に応じた規則を使うんだ。

丸が状態、文字の付いた矢印がその文字を読んだときの移動だよ。開始の矢印から進み、入力を全部読んだところで二重丸の受理状態にいれば受理する。図はNFAの例で、線がない入力では進めない。たとえばbbaaabは受理されるけれど、abの後にさらにaを足すと進めなくなるんだ。

DFAは各状態と入力記号の組み合わせに対して、次の状態が一つに決まる。NFAは進める先がゼロ・一つ・複数の場合があり、入力を読まないε遷移も使えるよ。どれか一つの経路で入力を全部読んで受理状態に着けば受理する。両者が認識できる言語の範囲は同じなんだ。

理論上の正規表現と有限オートマトンは、表せる言語の範囲が同じだよ。ただし実装の正規表現には後方参照などの拡張がある。たとえばPCRE2には、前に一致した文字列を参照する機能があるので、実際のエンジンをすべて単純な有限オートマトンと考えないようにしよう。

スタックを追加したプッシュダウンオートマトンは、括弧の入れ子のような構造を扱えるよ。チューリングマシンは、読み書きして左右へ動けるヘッドと、長さに上限のないテープを持つモデル。ただしそれでも判定できない問題がある。計算の能力だけでなく限界も考えるのが、この理論の役割なんだ。