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 words classes of and/or classes:
“There are four classes of idols which beset men’s minds. To these for distinction’s sake I have assigned names—calling the first class Idols of the Tribe; the second, Idols of the Cave; the third, Idols of the Market-Place; the fourth, Idols of the Theatre.”
—Francis Bacon (1561–1626)
“My plan of instruction is extremely simple and limited. They learn, on week-days, such coarse works as may fit them for servants. I allow of no writing for the poor. My object is not to make fanatics, but to train up the lower classes in habits of industry and piety.”
—Hannah More (1745–1833)
Related Phrases
Related Words