68Q15-ChomskyHierarchy.tex

\documentclass[12pt]{article}
\usepackage{pmmeta}
\pmcanonicalname{ChomskyHierarchy}
\pmcreated{2013-03-22 16:27:04}
\pmmodified{2013-03-22 16:27:04}
\pmowner{CWoo}{3771}
\pmmodifier{CWoo}{3771}
\pmtitle{Chomsky hierarchy}
\pmrecord{13}{38607}
\pmprivacy{1}
\pmauthor{CWoo}{3771}
\pmtype{Definition}
\pmcomment{trigger rebuild}
\pmclassification{msc}{68Q15}
\pmclassification{msc}{03D55}
\pmsynonym{Chomsky-Sch\"utzenberger hierarchy}{ChomskyHierarchy}
\pmsynonym{Chomsky-Schutzenberger hierarchy}{ChomskyHierarchy}
\pmsynonym{unrestricted grammar}{ChomskyHierarchy}
\pmdefines{type-0 grammar}
\pmdefines{type-0 language}

\endmetadata

\usepackage{amssymb,amscd}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{mathrsfs}
\usepackage{tabls}

% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%%%\usepackage{xypic}

% there are many more packages, add them here as you need them

% define commands here

\begin{document}
The {\em Chomsky hierarchy} or {\em Chomsky-Sch\"utzenberger 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
\begin{description}
\item[Type-0 grammar] if there are no restrictions on the productions.  Type-0 grammar is also known as an \emph{unrestricted grammar}, or a \emph{phrase-structure grammar}.
\item[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.
\item[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.
\item[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.
\end{description}
It is clear that every type-$i$ grammar is type-0, and every type-3 grammar is type-2.  A type-2 grammar is not necessarily type-1, 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$$
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.
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline\hline
grammar & language family & abbreviation & automaton \\
\hline\hline
type-0 & recursively enumerable & $\mathscr{L}_0$ or $\mathscr{E}$ & turing machine \\
\hline
type-1 & context-sensitive & $\mathscr{L}_1$ or $\mathscr{S}$ & linear bounded automaton \\
\hline
type-2 & context-free & $\mathscr{L}_2$ or $\mathscr{F}$ & pushdown automaton \\
\hline
type-3 & regular & $\mathscr{L}_3$ or $\mathscr{R}$ & finite automaton \\
\hline
\end{tabular}
\end{center}
%%%%%
%%%%%
\end{document}