Consider the following sets. Set of all recursively enumerable languages over the alphabet {0,1}

Q. Consider the following sets:

S1.       Set of all recursively enumerable languages over the alphabet {0,1}

S2.       Set of all syntactically valid C programs

S3.        Set of all languages over the alphabet {0,1}

S4.       Set of all non-regular languages over the alphabet {0,1}

Which of the above sets are uncountable?

(A) S1 and S2

(B) S3 and S4

(C) S2 and S3

(D) S1 and S4

Ans: S₃ and S₄

Solution:

1. Recursively enumerable languages are countable.
2. Syntactically valid C program can be represented with CFG. CFG generates CFL, CFL is countable.
3. All languages over {0, 1} may not be countable, because they may also lie in the region of 2^Σ*.
4. Set of regular languages are countable, non-regular languages may not be countable.