October 12, 2023
October 12, 2023
October 12, 2023
###### GATE 2023
October 12, 2023
 Question 3

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 S2 and S3 B S3 and S4 C S1 and S4 D S1 and S2
Question 3 Explanation:
S1 is countable, set of all recursively enumerable languages means set of all Turing machines and we can enumerate TM and have one to one correspondence between natural number.
S2 is countable, since a valid C program represents a valid algorithm and every algorithm corresponds to a Turing Machine, so S2 is equivalent to set of all Turing Machines.
S3 is is uncountable, it is proved by diagonalization method.
S4 is uncountable, as set of non-regular languages will have languages which is set of all languages over alphabet {0,1} i.e., S3.
Question 3 Explanation:
S1 is countable, set of all recursively enumerable languages means set of all Turing machines and we can enumerate TM and have one to one correspondence between natural number.
S2 is countable, since a valid C program represents a valid algorithm and every algorithm corresponds to a Turing Machine, so S2 is equivalent to set of all Turing Machines.
S3 is is uncountable, it is proved by diagonalization method.
S4 is uncountable, as set of non-regular languages will have languages which is set of all languages over alphabet {0,1} i.e., S3.