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:
“Genocide begins, however improbably, in the conviction that classes of biological distinction indisputably sanction social and political discrimination.”
—Andrea Dworkin (b. 1946)
“One marvels why ... the middle classes still insist on so much discomfort for their children at such expense to themselves.”
—E.M. (Edward Morgan)
Related Phrases
Related Words