オートマトン 【automaton】 状態機械 / state machine / オートマタ / automata

概要

解説 オートマトンは一定の規則に従って複数の内部「状態」（state）の間を「遷移」（transition）する仮想的な機械で、現在の状態と入力の組み合わせを規則の中から探し出し、指定された次の状態へ遷移する。規則に該当する組み合わせがなければ同じ状態を維持する。規則は状態遷移表や状態遷移図として書き表すことができる。

有限個の種類からなる状態と入力を扱うものを「有限オートマトン」（finite automaton）という。最も単純なモデルであるためよく考察の対象となり、論理回路の設計やプロトコル（通信規約）の検証、言語の構文解析など実用上の応用も盛んに行われている。

有限オートマトンのうち、状態と入力によって次の遷移先が常に一意に定まるものを「決定性有限オートマトン」（DFA：Deterministic Finite Automaton）、次の遷移先が一意に決まるとは限らないものを「非決定性有限オートマトン」（NFA：Nondeterministic Finite Automaton）という。

有限オートマトンに無限の深さのスタックを追加した「プッシュダウンオートマトン」（push down automaton）や、複数のオートマトンを並べて相互作用させる「セルオートマトン」（cell automaton）などもよく知られている。広義には「チューリングマシン」（Turing machine）もオートマトンと一種とみなす場合もある。