TheoryofComputation
October 12, 2023GATE 2023
October 12, 2023TheoryofComputation
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 nonregular languages over the alphabet {0,1}
Which of the above sets are uncountable?
S2 and S3


S3 and S4


S1 and S4


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 nonregular languages will have languages which is set of all languages over alphabet {0,1} i.e., S3.
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 nonregular languages will have languages which is set of all languages over alphabet {0,1} i.e., S3.
Correct Answer: B
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 nonregular languages will have languages which is set of all languages over alphabet {0,1} i.e., S3.
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 nonregular languages will have languages which is set of all languages over alphabet {0,1} i.e., S3.
Subscribe
Login
0 Comments