###### Theory-of-Computation

October 12, 2023###### GATE 2023

October 12, 2023# Theory-of-Computation

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?

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 non-regular 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 non-regular 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 non-regular 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 non-regular languages will have languages which is set of all languages over alphabet {0,1} i.e., S3.

Subscribe

Login

0 Comments