Chomsky hierarchy
The Chomsky hierarchy or ChomskySchü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=(\mathrm{\Sigma},N,P,\sigma )$ consists of an alphabet $\mathrm{\Sigma}$, an alphabet $N$ of nonterminal symbols properly included in $\mathrm{\Sigma}$, a nonempty finite set^{} $P$ of productions, and a symbol $\sigma \in N$ called the start symbol. The nonempty alphabet $T:=\mathrm{\Sigma}N$ is the set of terminal symbols. Then $G$ is called a
 Type0 grammar

if there are no restrictions^{} on the productions. Type0 grammar is also known as an unrestricted grammar, or a phrasestructure grammar.
 Type1 grammar

if the productions are of the form $uAv\to uWv$, where $u,v,W\in {\mathrm{\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 type1 grammar is also known as a contextsensitive grammar.
 Type2 grammar

if the productions are of the form $A\to W$, where $A\in N$ and $W\in {\mathrm{\Sigma}}^{*}$. Type2 grammars are also called contextfree grammars, because the left hand side of any productions are “free” of contexts.
 Type3 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 type3 grammars can be represented by regular expressions^{}, type3 grammars are also known as regular grammars.
It is clear that every type$i$ grammar is type0, and every type3 grammar is type2. A type2 grammar is not necessarily type1, because it may contain both $\sigma \to \lambda $ and $A\to W$, where $\lambda $ occurs in $W$. Nevertheless, the relevance of the hierarchy has more to do with the languages generated by the grammars. Call a formal language a type$i$ language if it is generated by a type$i$ grammar, and denote ${\mathcal{L}}_{i}$ the family of type$i$ languages. Then it can be shown that
$${\mathcal{L}}_{3}\subset {\mathcal{L}}_{2}\subset {\mathcal{L}}_{1}\subset {\mathcal{L}}_{0}$$ 
where each inclusion is strict.
Below is a table summarizing the four types of grammars, the languages they generate, and the equivalent^{} computational devices accepting the languages.
Title  Chomsky hierarchy 
Canonical name  ChomskyHierarchy 
Date of creation  20130322 16:27:04 
Last modified on  20130322 16:27:04 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  13 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 68Q15 
Classification  msc 03D55 
Synonym  ChomskySchützenberger hierarchy 
Synonym  ChomskySchutzenberger hierarchy 
Synonym  unrestricted grammar 
Defines  type0 grammar 
Defines  type0 language 
\@unrecurse 