NEW
New Website Launch
Experience the best way to solve previous year questions with mock tests (very detailed analysis), bookmark your favourite questions, practice etc...
VISIT NOW

GATE CSE

Undecidability

Theory of Computation

Previous Years Questions

Marks 1

More
Which of the following decision problems are undecidable? $$\,\,\,\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\,\,\,\,$$ Given $$...
GATE CSE 2016 Set 1
Let $$\sum \, $$ be a finite non - empty alphabet and let $${2^{\sum {{}^ * } }}$$ be the power set of $$\sum {{}^ * .\,...
GATE CSE 2014 Set 3
Which of the following problems are decidable? $$1.$$ Does a given program ever produce an output? $$2.$$ If L is a cont...
GATE CSE 2012
Which of the following are decidable? $$1.$$ Whether the intersection of two regular languages is infinite $$2.$$ Whethe...
GATE CSE 2008
Which of the following statements is false?
GATE CSE 1996

Marks 2

More
Which of the following languages are undecidable? Note that $$\langle M\rangle $$ indicates encoding of the Turing machi...
GATE CSE 2020
Language $${L_1}$$ is polynomial time reducible to language $${L_2}$$ . Language $${L_3}$$ is polynomial time reducible ...
GATE CSE 2015 Set 3
Which one of the following problems is un-decidable?
GATE CSE 2014 Set 3
Which of the following is/are undecidable? $$1.$$ $$G$$ is a $$CFG.$$ Is $$L\left( G \right) = \Phi ?$$ $$2.$$ $$G$$ is...
GATE CSE 2013
Consider three decision problems $${P_1},$$ $${P_2}$$ and $${P_3}.$$ It is known that $${P_1}$$ is decidable and $${P_2}...
GATE CSE 2005
Consider the following problem $$X.$$ Given a Turing machine $$M$$ over the input alphabet $$\sum , $$ any state $$q$$ o...
GATE CSE 2001
Which one of the following is the strongest correct statement about a finite language over some finite alphabet $$\sum ?...
GATE CSE 1991
It is decidable whether:
GATE CSE 1990
Which of the following problems are un-decidable?
GATE CSE 1989

Joint Entrance Examination

JEE Main JEE Advanced WB JEE

Graduate Aptitude Test in Engineering

GATE CSE GATE ECE GATE EE GATE ME GATE CE GATE PI GATE IN

Medical

NEET

CBSE

Class 12