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)
“Genocide begins, however improbably, in the conviction that classes of biological distinction indisputably sanction social and political discrimination.”
—Andrea Dworkin (b. 1946)
Related Phrases
Related Words