| Type-0 |
Unrestricted |
Recursively enumerable |
Turing machine |
| — |
(no common name) |
Decidable |
Decider |
| Type-1 |
Context-sensitive |
Context-sensitive |
Linear-bounded |
| — |
Positive range concatenation |
Positive range concatenation* |
PTIME Turing Machine |
| — |
Indexed |
Indexed* |
Nested stack |
| — |
— |
— |
Thread automaton |
| — |
Linear context-free rewriting systems |
Linear context-free rewriting language |
restricted Tree stack automaton |
| — |
Tree-adjoining |
Tree-adjoining |
Embedded pushdown |
| Type-2 |
Context-free |
Context-free |
Nondeterministic pushdown |
| — |
Deterministic context-free |
Deterministic context-free |
Deterministic pushdown |
| — |
Visibly pushdown |
Visibly pushdown |
Visibly pushdown |
| Type-3 |
Regular |
Regular |
Finite |
| — |
— |
Star-free |
Counter-free (with aperiodic finite monoid) |
| — |
Non-recursive |
Finite |
Acyclic finite |