# Grammar - Hierarchy of grammar (Chomsky)

In the formal languages (of computer science and linguistics), the Chomsky hierarchy is a hierarchy of formal grammars described by Noam Chomsky in 1956.

The hierarchy describes the relations between:

• various languages
• and their kinds of formalized logic.

## Definition

Grammar Languages Automaton Production rules (constraints)*
Type-0 Recursively enumerable Turing machine ${\displaystyle \alpha \rightarrow \beta }$ (where ${\displaystyle \alpha }$ contains at least one non-terminal)
Type-1 Context-sensitive Linear-bounded non-deterministic Turing machine ${\displaystyle \alpha A\beta \rightarrow \alpha \gamma \beta }$
Type-2 Context-free Non-deterministic pushdown automaton ${\displaystyle A\rightarrow \gamma }$
Type-3 Regular Finite state automaton ${\displaystyle A\rightarrow {\text{a}}}$ and ${\displaystyle A\rightarrow {\text{a}}B}$