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 }
A
L2 and L3 only
B
L1 and L3 only
C
L2, L3 and L4 only
D
L1, L3 and L4 only
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$$

A
$${\rm I}$$$${\rm I}$$ only
B
$${\rm III}$$ only
C
$${\rm I}$$ and $${\rm IV}$$ only
D
$${\rm I}$$ only
3
GATE CSE 2014 Set 3
MCQ (Single Correct Answer)
+2
-0.6
Which one of the following problems is un-decidable?
A
Deciding if a given context-free grammar is ambiguous.
B
Deciding if a given string is generated by a given context-free grammar.
C
Deciding if the language generated by a given context-free grammar is empty.
D
Deciding if the language generated by a given context-free grammar is finite.
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)?$$
A
$$3$$ only
B
$$3$$ and $$4$$ only
C
$$1,2$$ and $$3$$ only
D
$$2$$ and $$3$$ only
GATE CSE Subjects
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
CBSE
Class 12