# Chomsky Hierarchy doesn't make sense to me.

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?

Thanks.

-
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. – MJD Mar 26 '12 at 18:52
$\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.) – 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.