1
GATE CSE 2016 Set 1
+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
+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
+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
+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
EXAM MAP
Medical
NEET