The GATE Grind

GATE Theory of Computation: Turing Machines and Undecidability – Previous Year Questions

13 GATE previous year questions on Turing Machines and Undecidability (Theory of Computation, Computer Science) with answers and explanations, from every paper.

  1. GATE 2017 CS 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…
  2. GATE 2016 CS 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…
  3. GATE 2016 CS 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…
  4. GATE 2015 CS 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…
  5. GATE 2018 CS Q17 (1 mark, Multiple choice) – The set of all recursively enumerable languages is
  6. 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…
  7. 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.…
  8. 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\*?
  9. 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…
  10. GATE 2022 CS Q46 (2 marks, Multiple select) – Which of the following is/are undecidable?
  11. GATE 2021 CS 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?
  12. GATE 2021 CS 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 =…
  13. 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…