1
GATE CSE 2020
+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
+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
+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
+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
Theory of Computation
Operating Systems
Algorithms
Digital Logic
Database Management System
Data Structures
Computer Networks
Software Engineering
Compiler Design
Web Technologies
General Aptitude
Discrete Mathematics
Programming Languages
Computer Organization
EXAM MAP
Joint Entrance Examination