> For the complete documentation index, see [llms.txt](https://mandober.gitbook.io/math-debrief/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mandober.gitbook.io/math-debrief/600-toc/620-formal-language-theory/chomsky-hierarchy.md).

# Chomsky hierarchy

Automata theory: formal languages and formal grammars

Chomsky hierarchy describes the relations between various languages and kinds of formalized logic.

| Chom | Grammars     | Languages              | Abstract machines |
| ---- | ------------ | ---------------------- | ----------------- |
| Ty-0 | Unrestricted | Recursively enumerable | TM                |

* \| (no common name) | Decidable | Decider Ty-1| Context-sensitive | Context-sensitive | Linear-bounded
* \| Positive range concat| Positive range concat | PTIME TM
* \| Indexed | Indexed | Nested stack
* \| - | - | Thread automaton
* \| Linear CF rewrite sys| Linear CF rewrite lang| Restricted treestack aut
* \| Tree-adjoining | Tree-adjoining | Embedded PDA Ty-2| Context-free (CF) | Context-free | Nondeterministic PDA
* \| Deterministic CF | Deterministic CF | Deterministic PDA
* \| Visibly PDA | Visibly PDA | Visibly PDA Ty-3| Regular | Regular | Finite
* \| - | Star-free | Counter-free
* \| Non-recursive | Finite | Acyclic finite

Each category of languages, except those marked by an asterisk, is a proper subset of the category directly above it.

Any language in each category is generated by a grammar and by an automaton in the category in the same line.