Gate2019 cs Q44

0. Consider the following sets:
S₁Set of all recursively enumerable languages over the alphabet {0,1}
S₂ Set of all syntactically valid C programs
S₃ Set of all languages over the alphabet {0,1}
S₄ Set of all non-regular languages over the alphabet {0,1}
Which of the above sets are uncountable?

Answer
Comment
Array

Option : B
Explanation :
S₁: The set : L_RE is known to be countably infinite since it corresponds with set of turing machines.
S₂: 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₃: Set of all languages = 2^Σ which is known to be uncountable. Σ* countably infinite
⇒ 2^Σ is uncountable.
S₄: Set of all non-regular languages includes set : L_{NOT RE} which is uncountable infinite and hence is uncountable.
So, S₃ and S₄ are uncountable.

Forgot your password?

I agree with the Terms.