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.