| Chomsky hierarchy | Grammars | Languages | Abstract machines |
|---|---|---|---|
| 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 … |