The GATE Grind

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.

  1. GATE 2007 CS Q6 (1 mark, Multiple choice) – Which problem is undecidable?
  2. GATE 2008 CS Q10 (1 mark, Multiple choice) – Which are decidable? I. Whether intersection of two regular languages is infinite. II. Whether a given context-free language is regular. III. Whether…
  3. GATE 2008 CS Q13 (1 mark, Multiple choice) – If L and L are recursively enumerable, L is
  4. GATE 2008 CS Q44 (2 marks, Multiple choice) – 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?
  5. GATE 2008 CS Q48 (2 marks, Multiple choice) – Which is false?
  6. GATE 2009 CS Q14 (1 mark, Multiple choice) – Let A belong to NP. Which statement is TRUE?
  7. GATE 2021 CS (CS2) Q46 (2 marks, Multiple choice) – S1: Every infinite regular language has an undecidable language as a subset. S2: Every finite language is regular. Which are true?
  8. GATE 2015 CS (CS2) Q20 (1 mark, Multiple choice) – Which statements are true? I: The complement of every Turing-decidable language is Turing-decidable. II: Some language in NP is not Turing-decidable.…
  9. GATE 2010 CS Q27 (1 mark, Multiple choice) – L₁ is recursive. L₂,L₃ are recursively enumerable but nonrecursive. Which is NOT necessarily true?
  10. GATE 2011 CS Q18 (1 mark, Multiple choice) – Which pair has different expressive power?
  11. GATE 2013 CS Q27 (1 mark, Multiple choice) – Which are false? 1: Every nondeterministic TM has an equivalent deterministic TM. 2: TM-recognizable languages are closed under union and complement.…
  12. GATE 2013 CS Q28 (1 mark, Multiple choice) – 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…
  13. GATE 2013 CS Q51 (2 marks, Multiple choice) – 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…
  14. GATE 2012 CS Q14 (1 mark, Multiple choice) – Assuming P≠NP, which is true?
  15. GATE 2012 CS Q34 (1 mark, Multiple choice) – 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…
  16. GATE 2017 CS (CS2) Q51 (2 marks, Multiple choice) – 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…
  17. GATE 2016 CS (CS2) Q54 (2 marks, Multiple choice) – 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…
  18. GATE 2014 CS (CS3) Q26 (1 mark, Multiple choice) – Let be a finite nonempty alphabet and 2* the power set of *. Which is TRUE?
  19. GATE 2014 CS (CS3) Q45 (2 marks, Multiple choice) – Which problem is undecidable?
  20. GATE 2014 CS (CS2) Q26 (1 mark, Multiple choice) – A mB means A is mapping (many-one) reducible to B. Which implication is FALSE?
  21. GATE 2014 CS (CS2) Q45 (2 marks, Multiple choice) – Let M encode a Turing machine over 0,1. Let L=\ M:M accepts a string of length 2014\. L is .
  22. GATE 2014 CS (CS1) Q45 (2 marks, Multiple choice) – Let L be a language and L its complement. Which is NOT a viable possibility?
  23. GATE 2017 CS (CS1) Q49 (2 marks, Multiple choice) – 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…
  24. GATE 2016 CS (CS1) Q27 (1 mark, Multiple choice) – 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…
  25. GATE 2016 CS (CS1) Q54 (2 marks, Multiple choice) – 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…
  26. GATE 2015 CS (CS1) Q28 (1 mark, Multiple choice) – 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…
  27. GATE 2018 CS Q17 (1 mark, Multiple choice) – The set of all recursively enumerable languages is
  28. GATE 2018 CS Q46 (2 marks, Multiple choice) – 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…
  29. GATE 2019 CS Q44 (2 marks, Multiple choice) – 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.…
  30. GATE 2026 CS (CS2) Q13 (1 mark, Multiple choice) – Which one of the following statements is equivalent to the assertion: Turing machine M decides the language L \0,1\*?
  31. GATE 2025 CS (CS2) Q25 (1 mark, Multiple choice) – 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…
  32. GATE 2022 CS Q46 (2 marks, Multiple select) – Which of the following is/are undecidable?
  33. GATE 2021 CS (CS1) Q22 (1 mark, Multiple select) – Let M denote an encoding of an automaton M. Suppose that = \0,1\. Which of the following languages is/are NOT recursive?
  34. GATE 2021 CS (CS1) Q49 (2 marks, Multiple choice) – 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 =…
  35. GATE 2020 CS Q36 (2 marks, Multiple choice) – 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…