オートマトン

オートマトン (単数形: , 複数形: オートマタ（ ）) とは、自動人形などとも呼ばれる「オートマタ」と同じ語であるが、計算理論において、計算モデルに関して有限オートマトンなどの総称として使われる。また特に「オートマトン理論」と呼ばれる分野では、計算機械のうち計算可能性の点でチューリングマシンよりも制限されているものを特に指して言うこともある。
形式言語の階層とオートマトン.
何らかの言語（特に形式言語）の文法（形式文法）と、それを生成する生成規則と、それを受理するオートマトンの間には対応関係があり、また言語を（形式言語を）集合とした場合に部分集合になっているという関係が階層をなしている、という事実がある。詳細は形式言語の階層の記事およびチョムスキー階層の記事を参照。