Theory of Computation
Finite Automata and Regular Language
Marks 1Marks 2Marks 5
Push Down Automata and Context Free Language
Marks 1Marks 2
Undecidability
Marks 1Marks 2
Recursively Enumerable Language and Turing Machine
Marks 1Marks 2
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
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