0
$\begingroup$

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.

  • 0
    $\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.)2012-03-26

1 Answers 1

3

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.