The Chomsky hierarchy or Chomsky-Schützenberger hierarchy is a way of classifying formal grammars into four types, with the lower numbered types being more general.

Recall that a formal grammar $G=(\Sigma,N,P,\sigma)$ consists of an alphabet $\Sigma$ , an alphabet $N$ of non-terminal symbols properly included in $\Sigma$ , a non-empty finite set $P$ of productions, and a symbol $\sigma\in N$ called the start symbol. The non-empty alphabet $T:=\Sigma-N$ is the set of terminal symbols. Then $G$ is called a

Type-0 grammar

if there are no restrictions on the productions. Type-0 grammar is also known as an unrestricted grammar, or a phrase-structure grammar.

Type-1 grammar

if the productions are of the form $uAv \to uWv$ , where $u,v,W\in \Sigma^*$ with $W\ne \lambda$ , and $A\in N$ , or $\sigma\to \lambda$ , provided that $\sigma$ does not occur on the right hand side of any productions in $P$ . As $A$ is surrounded by words $u,v$ , a type-1 grammar is also known as a context-sensitive grammar.

Type-2 grammar

if the productions are of the form $A\to W$ , where $A\in N$ and $W\in \Sigma^*$ . Type-2 grammars are also called context-free grammars, because the left hand side of any productions are ``free'' of contexts.

Type-3 grammar

if the productions are of the form $A\to u$ or $A\to uB$ , where $A,B\in N$ and $u\in T^*$ . Owing to the fact that languages generated by type-3 grammars can be represented by regular expressions, type-3 grammars are also known as regular grammars.

Below is a table summarizing the four types of grammars, the languages they generate, and the equivalent computational devices accepting the languages.

grammar	language family	abbreviation	automaton
type-0	recursively enumerable	or	turing machine
type-1	context-sensitive	or	linear bounded automaton
type-2	context-free	or	pushdown automaton
type-3	regular	or	finite automaton