GATE CS 2019 Q34 — Regular and Context-free Languages

To determine which of the given sets are uncountable, let us analyze each set individually:

• $S_1$: Set of all recursively enumerable (RE) languages over $\{0, 1\}$

  Every recursively enumerable language is recognized by a Turing Machine. Since any Turing Machine can be represented as a finite-length string over a finite alphabet, the set of all Turing Machines is countably infinite. Consequently, the set of all RE languages ($S_1$) is countable.

• $S_2$: Set of all syntactically valid C programs

  Each syntactically valid C program is a finite-length string of characters chosen from a finite alphabet (ASCII). The set of all finite-length strings over a finite alphabet is countably infinite. Thus, $S_2$ is countable.

• $S_3$: Set of all languages over $\{0, 1\}$

  The set of all strings over $\{0, 1\}$, denoted by $\Sigma^*$, is countably infinite. The set of all languages over $\{0, 1\}$ is the power set of $\Sigma^*$, i.e., $2^{\Sigma^*}$. According to Cantor's theorem, the power set of a countably infinite set is uncountably infinite. Therefore, $S_3$ is uncountable.

• $S_4$: Set of all non-regular languages over $\{0, 1\}$

  The set of all languages ($S_3$) is the union of the set of regular languages ($L_{\text{reg}}$) and the set of non-regular languages ($S_4$):

  $$S_3 = L_{\text{reg}} \cup S_4$$

  Since every regular language can be represented by a finite regular expression, $L_{\text{reg}}$ is countable. If $S_4$ were also countable, then their union $S_3$ would have to be countable (as the union of two countable sets is countable). Since $S_3$ is uncountable, $S_4$ must be uncountable.

Thus, only $S_3$ and $S_4$ are uncountable sets.