GATE Theory of Computation: Turing Machines and Undecidability – Previous Year Questions
35 GATE previous year questions on Turing Machines and Undecidability (Theory of Computation, Computer Science) with answers and explanations, from every paper.
35 questions worth 51 marks in all (19 1-mark, 16 2-mark). Asked between 2007 and 2026, so you can see how the topic has been tested over time.
- GATE 2007 CS Q6 – Which problem is undecidable?
- GATE 2008 CS Q10 – Which are decidable? I. Whether intersection of two regular languages is infinite. II. Whether a given context-free language is regular. III. Whether…
- GATE 2008 CS Q13 – If L and L are recursively enumerable, L is
- GATE 2008 CS Q44 – Subset sum: given n positive integers S and positive W, determine whether a subset sums to W. Algorithm Q takes O(nW) time. Which is false?
- GATE 2008 CS Q48 – Which is false?
- GATE 2009 CS Q14 – Let A belong to NP. Which statement is TRUE?
- GATE 2021 CS (CS2) Q46 – S1: Every infinite regular language has an undecidable language as a subset. S2: Every finite language is regular. Which are true?
- GATE 2015 CS (CS2) Q20 – Which statements are true? I: The complement of every Turing-decidable language is Turing-decidable. II: Some language in NP is not Turing-decidable.…
- GATE 2010 CS Q27 – L₁ is recursive. L₂,L₃ are recursively enumerable but nonrecursive. Which is NOT necessarily true?
- GATE 2011 CS Q18 – Which pair has different expressive power?
- GATE 2013 CS Q27 – Which are false? 1: Every nondeterministic TM has an equivalent deterministic TM. 2: TM-recognizable languages are closed under union and complement.…
- GATE 2013 CS Q28 – Which are true? 1: Undirected cycle detection is in P. 2: Undirected cycle detection is in NP. 3: Every NP-complete problem has a nondeterministic…
- GATE 2013 CS Q51 – Which problems are undecidable? 1: Given CFG G, is L(G)=∅? 2: Given CFG G, is L(G)=Σ*? 3: Given TM M, is L(M) regular? 4: Given DFA A and NFA N, is…
- GATE 2012 CS Q14 – Assuming P≠NP, which is true?
- GATE 2012 CS Q34 – Which problems are decidable? 1: Does an arbitrary program ever output anything? 2: Given a CFL L, is L context-free? 3: Given regular L, is L…
- GATE 2017 CS (CS2) Q51 – L(R) is a regular-expression language, L(G) a context-free grammar language, L(M) a Turing-machine language. Which are undecidable? I: Given R,w, is…
- GATE 2016 CS (CS2) Q54 – Let L₁=⟨M⟩: M takes at least 2016 steps on some input, L₂=⟨M⟩: M takes at least 2016 steps on all inputs, L₃=⟨M⟩: M accepts ε, with ⟨M⟩ encoding a…
- GATE 2014 CS (CS3) Q26 – Let be a finite nonempty alphabet and 2* the power set of *. Which is TRUE?
- GATE 2014 CS (CS3) Q45 – Which problem is undecidable?
- GATE 2014 CS (CS2) Q26 – A mB means A is mapping (many-one) reducible to B. Which implication is FALSE?
- GATE 2014 CS (CS2) Q45 – Let M encode a Turing machine over 0,1. Let L=\ M:M accepts a string of length 2014\. L is .
- GATE 2014 CS (CS1) Q45 – Let L be a language and L its complement. Which is NOT a viable possibility?
- GATE 2017 CS (CS1) Q49 – Let A and B be finite alphabets and let \# be a symbol outside both A and B. Let f be a total function from A* to B*. We say f is *computable* if…
- GATE 2016 CS (CS1) Q27 – Which of the following decision problems are undecidable? I. Given NFAs N 1 and N 2, is L(N 1) L(N 2) = ? II. Given a CFG G = (N, , P, S) and a string…
- GATE 2016 CS (CS1) Q54 – Let X be a recursive language and Y be a recursively enumerable but not recursive language. Let W and Z be two languages such that Y reduces to W, and…
- GATE 2015 CS (CS1) Q28 – For any two languages L 1 and L 2 such that L 1 is context-free and L 2 is recursively enumerable but not recursive, which of the following is/are…
- GATE 2018 CS Q17 – The set of all recursively enumerable languages is
- GATE 2018 CS Q46 – Consider the following problems. L(G) denotes the language generated by a grammar G. L(M) denotes the language accepted by a machine M. (I) For an…
- GATE 2019 CS Q44 – Consider the following sets: S1. Set of all recursively enumerable languages over the alphabet 0,1 S2. Set of all syntactically valid C programs S3.…
- GATE 2026 CS (CS2) Q13 – Which one of the following statements is equivalent to the assertion: Turing machine M decides the language L \0,1\*?
- GATE 2025 CS (CS2) Q25 – Let G 1, G 2 be Context Free Grammars (CFGs) and R be a regular expression. For a grammar G, let L(G) denote the language generated by G. Which ONE…
- GATE 2022 CS Q46 – Which of the following is/are undecidable?
- GATE 2021 CS (CS1) Q22 – Let M denote an encoding of an automaton M. Suppose that = \0,1\. Which of the following languages is/are NOT recursive?
- GATE 2021 CS (CS1) Q49 – For a Turing machine M, M denotes an encoding of M. Consider the following two languages. L 1 = \ M M takes more than 2021 steps on all inputs\ L 2 =…
- GATE 2020 CS Q36 – Which of the following languages are undecidable? Note that M indicates encoding of the Turing machine M. L 1=\ M L(M)=\ L 2=\ M,w,q M on input w…