オートマトン (Automaton)
オートマトンとは、入力に応じた処理を行い、結果を出力する仮想的な自動機械です。オートマトンとは｜automaton - IT用語辞典 e-Words
| |
|
|
| 0型言語 |
チューリングマシン (Turing machine) |
|
| 1型言語 |
線形有界オートマトン (Linear Bounded Automaton : LBA) |
文脈依存言語 |
| 2型言語 |
プッシュダウン オートマトン (Pushdown Automaton : PDA) |
文脈自由言語 |
| 3型言語 |
有限オートマトン (Finite Automaton) |
正則言語 |
- Turing machine (Deterministic Turing machine : DTM)
- Non-deterministic Turing machine (NTM)
- Probabilistic Turing machine (PTM)
- Multitape Turing machine (MTM)
有限状態オートマトン (Finite-state Automaton : FSA) / 有限状態機械 (Finite-state Machine : FSM)
非決定性有限オートマトン (Non-deterministic Finite Automaton : NFA)