Chomsky Hierarchy

These are the types of formal grammars defined by Chomsky.

In the production rules, $a$ is a terminal symbol, $A, B$ are non-terminal symbols, and $\alpha, \beta, \gamma$ are strings of terminals and/or non-terminals.

This paraphrases the Wikipedia page for the Chomsky hierarchy.

Type-3

Regular.

Recognizing automaton: finite-state automaton

Production rules:

• $A \rightarrow a$
• $A \rightarrow aB$ (right regular)

or

• $A \rightarrow a$
• $A \rightarrow Ba$ (left regular)

Type-2

Context-free.

Recognizing automaton: non-deterministic pushdown automaton

Production rules:

• $A \rightarrow \alpha$

Type-1

Context-sensitive.

Recognizing automaton: linear-bounded non-deterministic Turing machine

Production rules:

• $\alpha A \beta \rightarrow \alpha \gamma \beta$

Type-0

Recursively enumerable.

Recognizing automaton: Turing machine

Production rules:

• $\gamma \rightarrow \alpha$