The Chomsky Hierarchy

We can now summarize the entire hierarchy of formal languages. We emphasize “hierarchy” because each language class is a subset of the class above it. This classification originated with Noam Chomsky and is aptly called the Chomsky hierarchy. See the following table.

We have yet to describe an RE language that is not recursive, and a language that is non-RE. Here we will show that there are more languages outside the Chomsky hierarchy (i.e., non-RE languages) than there are inside of it (the “recursively enumerable or better” languages). Our argument is based on the countability of infinite sets.

Countable sets

A set is countable if there is a one-to-one correspondence between its elements and the natural numbers, $\mathcal{N}$ (or a subset of $\mathcal{N}$). Any finite set is therefore countable, and an infinite set is countable if its elements can be enumerated. The set of strings $\{a,b\}^*$ is countably infinite because its elements can be arranged in a well-defined sequence (i.e., the familiar canonical order):

In this case, the subscripts are the natural numbers themselves, exhibiting the one-to-one correspondence between $\mathcal{N}$ and $\{a,b\}^*$ (i.e., $e(0)=\lambda, e(1)=a, e(2)=b, e(3)=aa,\cdots$).

We can conclude that all formal languages are countable sets, since they can be arranged in canonical order. A formal language is, after all, a subset of the countable set, $\Sigma^*$.

Remember: All formal languages are countable sets of strings.

Now, recall that Turing machines can be represented as strings over some alphabet. In particular, we know how to encode any $\text{TM}$ ...