Undecidability · Theory of Computation · GATE CSE
Start PracticeMarks 1
GATE CSE 2016 Set 1
Which of the following decision problems are undecidable?
$$\,\,\,\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\,\,\,\,$$ Given $$NFAs$$ $${N_1}$$ and $${N_2},$...
GATE CSE 2014 Set 3
Let $$\sum \, $$ be a finite non - empty alphabet and let $${2^{\sum {{}^ * } }}$$ be the power set of $$\sum {{}^ * .\,} $$ Which one of the followin...
GATE CSE 2012
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 $$...
GATE CSE 2008
Which of the following are decidable?
$$1.$$ Whether the intersection of two regular languages is infinite
$$2.$$ Whether a given context-free languag...
GATE CSE 1996
Which of the following statements is false?
Marks 2
GATE CSE 2020
Which of the following languages are undecidable? Note that $$\langle M\rangle $$ indicates encoding of the Turing machine M.
L1 = $$\left\{ {\langle ...
GATE CSE 2015 Set 3
Language $${L_1}$$ is polynomial time reducible to language $${L_2}$$ . Language $${L_3}$$ is polynomial time reducible to $${L_2}$$ , which in turn i...
GATE CSE 2014 Set 3
Which one of the following problems is un-decidable?
GATE CSE 2013
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 \ri...
GATE CSE 2005
Consider three decision problems $${P_1},$$ $${P_2}$$ and $${P_3}.$$ It is known that $${P_1}$$ is decidable and $${P_2}$$ is un-decidable. Which of t...
GATE CSE 2001
Consider the following problem $$X.$$ Given a Turing machine $$M$$ over the input alphabet $$\sum , $$ any state $$q$$ of $$M$$ And a word $$w\,\,\var...
GATE CSE 2000
Consider the following decision problems :
$${P_1}$$ Does a given finite state machine accept a given string
$${P_2}$$ Does a given context free gramm...
GATE CSE 1991
Which one of the following is the strongest correct statement about a finite language over some finite alphabet $$\sum ? $$
GATE CSE 1990
It is decidable whether:
GATE CSE 1989
Which of the following problems are un-decidable?