Chomsky hierarchy
Automata theory: formal languages and formal grammars
Chomsky hierarchy describes the relations between various languages and kinds of formalized logic.
| (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.
Last updated