オートマトン

オートマトン (単数形:  , 複数形: オートマタ（ ）) は、計算理論において有限オートマトンなどの総称。

また特に「オートマトン理論」と呼ばれる分野では、計算機械のうち計算可能性の点でチューリングマシンよりも制限されているものを特に指して言うこともある。

 種類 
有限オートマトン
決定的有限オートマトン (Deterministic Finite Automaton, DFA)
非決定的有限オートマトン (Nondeterministic Finite Automaton, NFA)
ε動作を含む非決定的有限オートマトン (Nondeterministic Finite Automaton, with ε transitions (FND-ε,ε-NFA))
プッシュダウン・オートマトン (Pushdown Automaton, PDA)
線形拘束オートマトン (Linear Bounded Automaton, LBA)
生け垣オートマトン (Hedge Automata)
 形式言語の階層とオートマトン 

何らかの言語（特に形式言語）の文法（形式文法）と、それを生成する生成規則と、それを受理するオートマトンの間には対応関係があり、また言語を（形式言語を）集合とした場合に部分集合になっているという関係が階層をなしている。詳細は形式言語の階層の記事およびチョムスキー階層の記事を参照。

 参考文献 
 米田政明 他 『オートマトン・言語理論の基礎』、 近代科学社、2003年、
 岩間 一雄：「オートマトン・言語と計算理論」、コロナ社、ISBN 978-4339018219（2003年10月）。
 藤原暁宏：「はじめて学ぶ　オートマトンと言語理論」、森北出版、ISBN 978-4-627-85291-4 (2015年7月21日)。


 関連項目 
 抽象機械
 セル・オートマトン
 状態機械
 正規表現
 形式文法

*
Category:計算理論
Category:計算モデル
Category:形式言語
Category:数学に関する記事