According to Chomsky, there are 4 types of grammar
Let $V = \text{set of non-terminals}$ and $T = \text{set of terminals}$
(a) $\text{Type-3}$ grammar
- These grammars generate regular language.
- In this grammar every production is of the form
$A \rightarrow xB$ or $A \rightarrow x$, where $A, B \in V$ and $x \in T$ (This is right linear grammar)
$A \rightarrow Bx$ or $A \rightarrow x$, where $A, B \in V$ and $x \in T$ (This is left linear grammar)
Every production of $\text{Type-3}$ grammar must either be right linear or left linear.
(b) $\text{Type-2}$ grammar
- These grammars generate context-free language.
- Every production of $\text{Type-2}$ grammar must be of the form
$A \rightarrow \alpha$, where $\alpha \in (V \cup T)^*$ and $A \in V$
(c) $\text{Type-1}$ grammar
- These grammars generate context-sensitive language.
- The productions must be in the form
$\alpha A\beta \rightarrow \alpha \gamma \beta$
where $A \in V$ and $\alpha \beta \gamma \in (V \cup T)^*$, the strings $\alpha, \beta$ may be empty but $\gamma$ must not be empty
(d) $\text{Type-0}$ grammar
- These grammars generate Recursively enumerable language.
- The productions must be in the form
$\alpha \rightarrow \beta$
where $\alpha, \beta \in (V \cup T)^* $ and $\alpha$ cannot be null and must contain atleast one non-terminal.