1
GATE CSE 2020
MCQ (Single Correct Answer)
+2
-0.67
Which of the following languages are undecidable? Note that $$\langle M\rangle $$ indicates encoding of the Turing machine M.
L1 = $$\left\{ {\langle M\rangle |L\left( M \right) = \phi } \right\}$$
L2 = $$\{ \langle M,w,q\rangle |$$ M on input w reaches state q in exactly 100 steps }
L3 = { $$\langle M\rangle |$$ L(M) is not recursive }
L4 = { $$\langle M\rangle |$$ L(M) contains at least 21 members }
L1 = $$\left\{ {\langle M\rangle |L\left( M \right) = \phi } \right\}$$
L2 = $$\{ \langle M,w,q\rangle |$$ M on input w reaches state q in exactly 100 steps }
L3 = { $$\langle M\rangle |$$ L(M) is not recursive }
L4 = { $$\langle M\rangle |$$ L(M) contains at least 21 members }
2
GATE CSE 2015 Set 3
MCQ (Single Correct Answer)
+2
-0.6
Language $${L_1}$$ is polynomial time reducible to language $${L_2}$$ . Language $${L_3}$$ is polynomial time reducible to $${L_2}$$ , which in turn is polynomial time reducible to language $${L_4}$$ . Which of the following is/are true?
$$\,\,\,\,\,\,\,\,\,\,\,\,\,\,{\rm I}.\,\,\,\,$$ if $$\,\,\,{L_4} \in P,$$ then $$\,\,\,{L_2} \in P$$
$$\,\,\,\,\,\,\,\,\,\,\,\,{\rm I}{\rm I}.\,\,\,\,$$ if $$\,\,\,{L_1} \in P$$ or $$\,\,\,{L_3} \in P,$$ then $$\,\,\,{L_2} \in P$$
$$\,\,\,\,\,\,\,\,\,\,{\rm I}{\rm I}{\rm I}.\,\,\,\,$$ if $$\,\,\,{L_1} \in P,$$ and only $$\,\,\,{L_3} \in P$$
$$\,\,\,\,\,\,\,\,\,\,{\rm I}V.\,\,\,\,$$ if $$\,\,\,{L_4} \in P,$$ then $$\,\,\,{L_1} \in P$$ and $$\,\,\,{L_3} \in P$$
3
GATE CSE 2014 Set 3
MCQ (Single Correct Answer)
+2
-0.6
Which one of the following problems is un-decidable?
4
GATE CSE 2013
MCQ (Single Correct Answer)
+2
-0.6
Which of the following is/are undecidable?
$$1.$$ $$G$$ is a $$CFG.$$ Is $$L\left( G \right) = \Phi ?$$
$$2.$$ $$G$$ is a $$CFG.$$ Is $$L\left( G \right) = \sum {{}^ * } ?$$
$$3.$$ $$M$$ is a Turing Machine. Is $$L(M)$$ regular?
$$4.$$ $$A$$ is a $$DFA$$ and $$N$$ is an $$NFA.$$
Is $$L(A)=L(N)?$$
$$1.$$ $$G$$ is a $$CFG.$$ Is $$L\left( G \right) = \Phi ?$$
$$2.$$ $$G$$ is a $$CFG.$$ Is $$L\left( G \right) = \sum {{}^ * } ?$$
$$3.$$ $$M$$ is a Turing Machine. Is $$L(M)$$ regular?
$$4.$$ $$A$$ is a $$DFA$$ and $$N$$ is an $$NFA.$$
Is $$L(A)=L(N)?$$
Questions Asked from Undecidability (Marks 2)
Number in Brackets after Paper Indicates No. of Questions
GATE CSE Subjects
Theory of Computation
Operating Systems
Algorithms
Database Management System
Data Structures
Computer Networks
Software Engineering
Compiler Design
Web Technologies
General Aptitude
Discrete Mathematics
Programming Languages