Explanation: Chomsky's Hierarchy of Languages

(related to Chapter: Classification of Formal Languages)

The definitions of the previously introduced types of grammars get (from type-3, over type-2 and type-1, to type-0) more and more general. This structure became known as the Chomsky hierarchy1.


The question arises, whether or not these generalizations induce proper inclusions of the language classes generated by the grammars, i.e. if $$\mathcal L_3\subseteq\mathcal L_2\subseteq\mathcal L_1\subseteq\mathcal L_0,$$ or if $$\mathcal L_3\subset\mathcal L_2\subset\mathcal L_1\subset\mathcal L_0.$$

The following examples demonstrate that the inclusions are, indeed, proper. For instance, all regular languages are context-free languages but not vice-versa.

Example of a Regular Language ($\in\mathcal L_3\subset\mathcal L_2\subset\mathcal L_1\subset\mathcal L_0$)

Example of a Context-Free, Not Regular Language ($\not\in\mathcal L_3$ and $\in\mathcal L_2\subset\mathcal L_1\subset\mathcal L_0$)

Example of a Context-sensitive, Not Context-free Language ($\not\in\mathcal L_3,\not\in\mathcal L_2,$ and $\in\mathcal L_1\subset\mathcal L_0$)

Example of a Recursively-Enumarable, Not Context-Sensitive Language ($\not\in\mathcal L_3,\not\in\mathcal L_2,\not\in\mathcal L_1,$ and $\in\mathcal L_0$)

An example can be a language, the words of which code a terminating Turing machine. We will see later what it is and why this language is not context-sensitive.

Thank you to the contributors under CC BY-SA 4.0!




  1. Erk, Katrin; Priese, Lutz: "Theoretische Informatik", Springer Verlag, 2000, 2nd Edition
  2. Hoffmann, Dirk: "Theoretische Informatik, 3. Auflage", Hanser, 2015


  1. see Noam Chomsky, 'Syntactic Structure', 1957