GATE CS 1997 Q3.4 — Regular and Context-free Languages

To determine which set is not countable, let us analyze each option given that $\Sigma = \{a, b\}$ is a finite alphabet:

1. Set of all strings over $\Sigma$ ($\Sigma^*$): Since $\Sigma$ is finite, the set of all finite-length strings $\Sigma^*$ is countably infinite. This set is countable.
2. Set of all languages over $\Sigma$ ($2^{\Sigma^*}$): A language is a subset of $\Sigma^*$. The set of all languages is the power set of $\Sigma^*$, denoted as $2^{\Sigma^*}$. By Cantor's theorem, the power set of a countably infinite set is uncountably infinite. Thus, this set is not countable.
3. Set of all regular languages over $\Sigma$: Every regular language can be represented by at least one regular expression (which is a finite string over a finite set of symbols). Since the set of all such strings is countable, the set of all regular languages is countable.
4. Set of all languages accepted by Turing machines: Each Turing machine can be uniquely encoded as a finite binary string. Since the set of all binary strings is countable, the set of all Turing machines is countable. Consequently, the set of recursively enumerable languages (languages accepted by Turing machines) is also countable.

Therefore, the set of all languages over $\Sigma$ is the only uncountable set among the choices.