Each language class on this table is a proper subset of the class above it.
[Type 0] Recursively Enumerable Languages -
Turing Machines
The most powerful machine, the Turing Machine is the equivalent of a computer with infinite memory.
[Type 1] Context-Sensitive Languages -
Linear Bounded Automata
The Linear Bounded Automaton is like a Turing Machine, but with a finite amount of memory linearly based on the size of the input.
[Type 2] Context-Free Languages -
Pushdown Automata
A Pushdown Automaton is a non-deterministic machine with a finite set of states and a limitless stack.
[Type 3] Regular Languages -
Deterministic Finite Automata
A Finite Automaton is a machine with a finite number of states that transitions based only its rules and the next input character.
