Question

Consider the following sets:
$S_1:$ Set of all recursively enumerable languages over the alphabet {0,1}.
$S_2:$ Set of all syntactically valid C programs.
$S_3:$ Set of all languages over the alphabet {0,1}.
$S_4:$ Set of all non-regular language over the alphabet {0,1}
Which of the above sets are uncountable?

Answer 1

$S_1:$ The set $L_{RE}$ is known to be countably infinite since it corresponds with set of turing machines.
$S_2:$ Since syntactically valid C programs surely run on Turing machines, this set is also a subset of set of Turing machines, which is countable.
$S_3:$ Set of all languages =$2^{\sum }{}^{\ast }$ which is known to be uncountable.$\sum \ast$ countably infinite
$\Rightarrow$$2^{\sum }{}^{\ast }$ is uncountable.
$S_4:$ Set of all non-regular languages includes set $L_{NOTRE}$ which is uncountable infinite and hence is uncountable.
So, $S_3$ and $S_4$ are uncountable.