Chomsky hierarchy

Definition

Let $G = (N, \Sigma, P, S)$ be a formal grammar, with $A, B \in N$, $a \in \Sigma$, and $\alpha, \beta, \gamma \in (N \cup \Sigma)^*$. The grammar $G$ is of:

1. type 0 always; these are the unrestricted grammars;
2. type 1 if every rule has the form $\alpha A \beta \to \alpha \gamma \beta$ with $\gamma$ nonempty, except possibly $S \to \varepsilon$ when $S$ occurs on no right side;
3. type 2 if every rule has the form $A \to \gamma$;
4. type 3 if every rule has the form $A \to aB$, $A \to a$ or $A \to \varepsilon$.

A language is of type $i$ if it is generated by a grammar of type $i$. The Chomsky hierarchy is the chain of the four classes of languages of types $3, 2, 1, 0$.