GATE CSE
Theory of Computation
Undecidability
Previous Years Questions

## Marks 1

Which of the following decision problems are undecidable? $$\,\,\,\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\,\,\,\,$$ Given $$NFAs$$ $${N_1}$$ and $${N_2},... Let$$\sum \, $$be a finite non - empty alphabet and let$${2^{\sum {{}^ * } }}$$be the power set of$$\sum {{}^ * .\,} $$Which one of the followin... 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$$...
Which of the following are decidable? $$1.$$ Whether the intersection of two regular languages is infinite $$2.$$ Whether a given context-free languag...
Which of the following statements is false?

## Marks 2

Which of the following languages are undecidable? Note that $$\langle M\rangle$$ indicates encoding of the Turing machine M. L1 = $$\left\{ {\langle ... 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... Which one of the following problems is un-decidable? 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...
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...
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... Which one of the following is the strongest correct statement about a finite language over some finite alphabet$$\sum ? 
It is decidable whether:
Which of the following problems are un-decidable?
EXAM MAP
Joint Entrance Examination