ChomskyHierarchy 2006-12-08 17:22:52 2009-07-25 22:41:12 Definition type-0 grammar type-0 language \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 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}