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.

-

2
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

1 Answer

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 24, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9116697311401367, "perplexity_flag": "head"}