Question

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?

1. S1 and S2
2. S3 and S4
3. S2 and S3
4. S1 and S4

Answer 1

Correct Answer - Option 2 : S3 and S4

• Every Recursively enumerable language has a Turing Machine, and a set of all Turing Machine's is countable. Therefore, the set of all Recursively enumerable languages is countable.
• There exists a one to one equivalence for all valid C programs and all valid TM encodings. Since the set of all valid TM encodings is countable, it means that the set of all syntactically valid C programs is also countable.
• Set of all languages is uncountable and the set of all Regular Languages is countable. So, the set of all non-regular languages should be uncountable as the union of two countable sets cannot make an uncountable set.

S3 and S4 are uncountable sets.

Important Points:

Every TM can be encoded with 0's and 1's, that is, every TM can be represented by a unique binary number.

Σ = {0,1} then set of all binary strings = Σ^∗. Σ^∗ is countable → Set of all TM's is countable.