有限オートマトンとは

有限オートマトンとは、有限個の状態と遷移と動作の組み合わせからなる数学的モデルです。
オートマトンは、ギリシア語の「自動的に動くもの」に由来し、機械仕掛けの人形や動物を意味します。ある目的にかなった複雑な動作をする機械を指し、例えば自動販売機・ロボット・電卓などを含みます。
転じて、入力(情報)と出力(応答・動作)の間に明確な関数関係があり、入力に対する認識と判断の機構と適切な出力を自動的にもつ数学的モデルを意味します。

有限オートマトンには、

• アクセプタ・リコグナイザ
• トランスデューサ

の２種類があります。
前者では入力を受容・理解し、外界に結果を知らせるために状態を用いるのに対し、後者では与えられた入力と動作を伴う状態に基づいて出力を生成します。

有限オートマトンはノード(節)とエッジ(矢印)からなる状態遷移図を用いて図示されます。
ノードは状態、エッジは遷移をそれぞれ表します。
有限個の入力記号が定められ、現在の内部状態と入力記号によって、次の瞬間における出力と内部状態が決定されます。
すべての入力を読み終えた時に受理状態にあればその入力を受理し、 受理状態ではなければ入力を拒否します。

別の区分では、ひとつの入力記号について遷移先が一意に決定する決定性有限オートマトン(DFA)と、ひとつの入力記号について遷移先が複数存在する非決定性有限オートマトン(NFA)に分けられます。
全ての非決定性有限オートマトンは、等価な決定性有限オートマトンに変換可能です。

有限オートマトンは、その性質から文字列を認識することが出来、一つの有限オートマトンが与えられると受理される文字列の一つの集合が定まります。
受理される文字列の集合を正規集合、文字列の集合を一つの文字列で表現する方法を正規表現とそれぞれ呼びます。
正規表現を用いると、複雑な文字列検索が効率的になります。正規文法から生成され、正規表現で記述でき、有限オートマトンで受理できる言語を正規言語と呼びます。

有限オートマトンに特別の記憶装置(スタック)をつけたものを、プッシュダウン・オートマトンといいます。
プッシュダウン・オートマトンは再帰的な構造を記述でき、正規表現よりも強力な表現力を持つ正規言語(文脈自由言語)を認識できます。

有限オートマトンは、デジタル回路・プログラム・半導体・通信プロトコルの設計など工学面のほか、神経系や自然言語の文法のモデル化などに応用されています。