You are here
HomeChomsky hierarchy
Primary tabs
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=(\Sigma,N,P,\sigma)$ consists of an alphabet $\Sigma$, an alphabet $N$ of nonterminal symbols properly included in $\Sigma$, a nonempty finite set $P$ of productions, and a symbol $\sigma\in N$ called the start symbol. The nonempty alphabet $T:=\SigmaN$ 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\Sigma^{*}$ with $W\neq\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\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 $\mathscr{L}_{i}$ the family of type$i$ languages. Then it can be shown that
$\mathscr{L}_{3}\subset\mathscr{L}_{2}\subset\mathscr{L}_{1}\subset\mathscr{L}_% {0}$ 
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 

type0  recursively enumerable  $\mathscr{L}_{0}$ or $\mathscr{E}$  turing machine 
type1  contextsensitive  $\mathscr{L}_{1}$ or $\mathscr{S}$  linear bounded automaton 
type2  contextfree  $\mathscr{L}_{2}$ or $\mathscr{F}$  pushdown automaton 
type3  regular  $\mathscr{L}_{3}$ or $\mathscr{R}$  finite automaton 
Mathematics Subject Classification
68Q15 no label found03D55 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections