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:
“I am ... by tradition and long study a complete snob. P. Marlowe and I do not despise the upper classes because they take baths and have money; we despise them because they are phony.”
—Raymond Chandler (1888–1959)