Automata Theory - Classes of Automata

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)

    “The want of education and moral training is the only real barrier that exists between the different classes of men. Nature, reason, and Christianity recognize no other. Pride may say Nay; but Pride was always a liar, and a great hater of the truth.”
    —Susanna Moodie (1803–1885)