1
GATE CSE 2016 Set 1
MCQ (Single Correct Answer)
+1
-0.3
Which of the following decision problems are undecidable?

$$\,\,\,\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\,\,\,\,$$ Given $$NFAs$$ $${N_1}$$ and $${N_2},$$ is $$L\left( {{N_1}} \right) \cap L\left( {{N_2}} \right) = \Phi ?$$
$$\,\,\,\,\,\,\,\,{\rm I}{\rm I}.\,\,\,\,\,\,\,\,\,\,$$Given a $$CFG\,G = \left( {N,\sum {\,,P} ,S} \right)$$ and string $$x \in \sum {^ * } ,$$ does
$$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$ $$x \in L\left( G \right)?$$
$$\,\,\,\,\,\,{\rm I}{\rm I}{\rm I}.\,\,\,\,\,\,\,\,\,\,$$ Given $$CFGs\,\,{G_1}$$ and $${G_2},$$ is $$L\left( {{G_1}} \right) = L\left( {{G_2}} \right)?$$
$$\,\,\,\,\,\,{\rm I}V.\,\,\,\,\,\,\,\,\,\,$$ Given a $$TM$$ $$M,$$ is $$L\left( M \right) = \Phi ?$$

A
$${\rm I}$$ and $${\rm IV}$$ only
B
$${\rm II}$$ and $${\rm I}$$$${\rm I}$$$${\rm I}$$ only
C
$${\rm I}$$$${\rm I}$$$${\rm I}$$ and $${\rm IV}$$ only
D
$${\rm II}$$ and $${\rm IV}$$ only
2
GATE CSE 2014 Set 3
MCQ (Single Correct Answer)
+1
-0.3
Let $$\sum \, $$ be a finite non - empty alphabet and let $${2^{\sum {{}^ * } }}$$ be the power set of $$\sum {{}^ * .\,} $$ Which one of the following is TRUE?
A
Both $${2^{\sum {{}^ * } }}$$ and $$\sum {^ * } $$ are countable
B
$${2^{\sum {{}^ * } }}$$ is countable and $$\sum {^ * } $$ is uncountable
C
$${2^{\sum {{}^ * } }}$$ is uncountable and $$\sum {^ * } $$ is countable
D
Both $${2^{\sum {{}^ * } }}$$ and $$\sum {^ * } $$ are uncountable
3
GATE CSE 2012
MCQ (Single Correct Answer)
+1
-0.3
Which of the following problems are decidable?
$$1.$$ Does a given program ever produce an output?
$$2.$$ If L is a context-free language, then, is $$\overline L $$ also context-free?
$$3.$$ If L is a regular language, then, is $$\overline L $$ also regular?
$$4.$$ If L is a recursive language, then, is $$\overline L $$ also recursive?
A
$$1, 2,3,4$$
B
$$1,2$$
C
$$2,3,4$$
D
$$3,4$$
4
GATE CSE 2008
MCQ (Single Correct Answer)
+1
-0.3
Which of the following are decidable?
$$1.$$ Whether the intersection of two regular languages is infinite
$$2.$$ Whether a given context-free language is regular
$$3.$$ Whether two push-down automata accept the same language
$$4.$$ Whether a given grammar is context-free
A
$$1$$ and $$2$$
B
$$1$$ and $$4$$
C
$$2$$ and $$3$$
D
$$2$$ and $$4$$
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
Defence
NDA
CBSE
Class 12