Wiki Article: Chomsky Hierarchy

In this containment hierarchy regular languages are a subset of context-sensitive languages. But let $\sum$ be the alphabet we're using. Then $\sum^*$ is a regular language that contains all languages on $\sum$. So it seems to me that we should think of regular languages as the more broad languages and context-sensitive languages as more specific.

How do I resolve this?


  • 2
    $\begingroup$ The containment hierarchy is about containment of one class of languages within another class, but your $\Sigma^*$ observation is about containment of one language within another language. $\endgroup$ – MJD Mar 26 '12 at 18:52
  • $\begingroup$ $\Sigma^*$ is also a context-free language. In fact every regular language is context-free. So the context-free languages are a more general class than the regular languages. (Brian's answer gives more detail.) $\endgroup$ – Tara B Mar 26 '12 at 22:13

Let an alphabet $\Sigma$ be given, and define $\Sigma^*$ in the usual way. Now let $\mathscr{L}=\wp(\Sigma^*)$, the collection of all subsets of $\Sigma^*$; the members of $\mathscr{L}$ are the languages over the alphabet $\Sigma$. (In other words, the languages over $\Sigma$ are precisely the subsets of $\Sigma^*$.) The Chomsky hierarchy distinguishes certain subfamilies of $\mathscr{L}$:

$$\begin{align*} \mathscr{L}_0&=\{L\in\mathscr{L}:\text{some formal grammar over }\Sigma\text{ generates }L\}\\ \mathscr{L}_1&=\{L\in\mathscr{L}:\text{some context-sensitive grammar over }\Sigma\text{ generates }L\}\\ \mathscr{L}_2&=\{L\in\mathscr{L}:\text{some context-free grammar over }\Sigma\text{ generates }L\}\\ \mathscr{L}_3&=\{L\in\mathscr{L}:\text{some regular grammar over }\Sigma\text{ generates }L\} \end{align*}$$

These are all subfamilies of $\mathscr{L}$: they are collections of languages, and it can be shown that $$\mathscr{L}_3\subsetneq\mathscr{L}_2\subsetneq\mathscr{L}_1\subsetneq\mathscr{L}_0\subsetneq\mathscr{L}$$ (provided that $|\Sigma|\ge 2$).

$\Sigma^*$, on the other hand, is not a collection of languages: it’s a single language that happens to belong to $\mathscr{L}_3$. It’s perfectly true that every $L\in\mathscr{L}$ is a subset of $\Sigma^*$, but the class $\mathscr{L}_3$ of regular languages is not closed under taking subsets: it’s entirely possible for a regular language to have a non-regular language as a subset. In particular, the fact that every language over $\Sigma$ is a subset of the regular language $\Sigma^*$ says nothing at all about the inclusiveness of the class $\mathscr{L}_3$ of regular languages. It simply happens to be the case that the most restrictive class of languages in the hierarchy turns out to contain the most inclusive single language.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.