Classes of Automata
The following is an incomplete list of types of automata.
| Automaton | Recognizable language |
|---|---|
| Nondeterministic/Deterministic Finite state machine (FSM) | regular languages |
| Deterministic pushdown automaton (DPDA) | deterministic context-free languages |
| Pushdown automaton (PDA) | context-free languages |
| Linear bounded automaton (LBA) | context-sensitive languages |
| Turing machine | recursively enumerable languages |
| Deterministic Büchi automaton | ω-limit languages |
| Nondeterministic Büchi automaton | ω-regular languages |
| Rabin automaton, Streett automaton, Parity automaton, Muller automaton | ω-regular languages |
Read more about this topic: Automata Theory
Famous quotes containing the word classes:
“The difference between people isn’t in their class, but in themselves. Only from the middle classes one gets ideas, and from the common people—life itself, warmth. You feel their hates and loves.”
—D.H. (David Herbert)
Related Phrases
Related Words