オートマトン
提供: miniwiki
オートマトン (単数形: 英: automaton [ɔːˈtɑməˌtɑn], 複数形: オートマタ（automata [ɔːˈtɑmətə]）) とは、自動人形などとも呼ばれる「オートマタ」と同じ語であるが、計算理論において、計算モデルに関して有限オートマトンなどの総称として使われる。また特に「オートマトン理論」と呼ばれる分野では、計算機械のうち計算可能性の点でチューリングマシンよりも制限されているものを特に指して言うこともある。
Contents
種類
- 有限オートマトン
- 決定的有限オートマトン (Deterministic Finite Automata (DFA))
- 非決定的有限オートマトン (Nondeterministic Finite Automata (NFA))
- ε動作を含む非決定的有限オートマトン (Nondeterministic Finite Automata, with ε transitions (FND-ε,ε-NFA))
- プッシュダウン・オートマトン (Pushdown Automata (PDA))
- 線形拘束オートマトン (Linear Bounded Automaton (LBA))
- 生け垣オートマトン(Hedge Automata)
（広義のオートマトン）
- チューリングマシン (Turing Machine)
- 決定的チューリングマシン(Deterministic Tuning Machine (DTM))
- 非決定的チューリングマシン(Nondeterministic Tuning Machine (NTM))
形式言語の階層とオートマトン
"「形式言語の階層」"
何らかの言語（特に形式言語）の文法（形式文法）と、それを生成する生成規則と、それを受理するオートマトンの間には対応関係があり、また言語を（形式言語を）集合とした場合に部分集合になっているという関係が階層をなしている、という事実がある。詳細は形式言語の階層の記事およびチョムスキー階層の記事を参照。
参考文献
- 『オートマトン・言語理論の基礎』 米田政明 他 近代科学社 2003年 ISBN 4764902974
- 『Switching and Finite Automata Theory』 Zvi Kohavi, Niraj K. Jha Cambridge University Press 2009年 ISBN 0521857481