The GATE Grind

GATE Theory of Computation: Regular and Context-Free Languages, Pumping Lemma – Previous Year Questions

17 GATE previous year questions on Regular and Context-Free Languages, Pumping Lemma (Theory of Computation, Computer Science) with answers and explanations, from every paper.

  1. GATE 2017 CS Q48 (2 marks, Multiple choice) – Consider the following languages over the alphabet = \a, b, c\. Let L 1 = \an bn cm m, n 0\ and L 2 = \am bn cn m, n 0\. Which of the following are…
  2. GATE 2019 CS Q17 (1 mark, Multiple choice) – If L is a regular language over = a,b , which one of the following languages is NOT regular?
  3. GATE 2019 CS Q25 (1 mark, Multiple choice) – For =\a,b\, let us consider the regular language L=\x x=a2+3k or x=b10+12k,\ k0\. Which one of the following can be a pumping length (the constant…
  4. GATE 2025 CS (CS2) Q24 (1 mark, Multiple choice) – Which ONE of the following languages is accepted by a deterministic pushdown automaton?
  5. GATE 2025 CS (CS2) Q30 (1 mark, Multiple select) – Consider the two lists List I and List II given below: List I List II --- --- (i) Context free languages (a) Closed under union (ii) Recursive…
  6. GATE 2025 CS (CS2) Q52 (2 marks, Multiple select) – Let = \a, b, c\. For x *, and , let \# (x) denote the number of occurrences of in x. Which one or more of the following option(s) define(s) regular…
  7. GATE 2025 CS (CS1) Q44 (2 marks, Multiple choice) – Consider the following two languages over the alphabet \a,b\: L 1 = \ \a,b\+ AND \a,b\+ \ L 2 = \ \a\+ AND \a,b\+ \ Which ONE of the following…
  8. GATE 2025 CS (CS1) Q45 (2 marks, Multiple choice) – Consider the following two languages over the alphabet \a,b,c\, where m and n are natural numbers. L 1 = \am bm cm+n m,n 1\ L 2 = \am bn cm+n m,n 1\…
  9. GATE 2024 CS (CS1) Q23 (1 mark, Multiple select) – Let L 1,L 2 be two regular languages and L 3 a language which is not regular. Which of the following statements is/are always TRUE?
  10. GATE 2023 CS Q24 (1 mark, Multiple select) – Which of the following statements is/are CORRECT?
  11. GATE 2022 CS Q23 (1 mark, Multiple select) – Which of the following statements is/are TRUE?
  12. GATE 2022 CS Q47 (2 marks, Multiple select) – Consider the following languages: L 1=\anwan w\a,b\*\ L 2=\wxwR w,x\a,b\*, w , x >0\ Note that wR is the reversal of the string w. Which of the…
  13. GATE 2022 CS Q48 (2 marks, Multiple select) – Consider the following languages: L 1=\ww w\a,b\*\ L 2=\anbncm m,n0\ L 3=\ambncn m,n0\ Which of the following statements is/are FALSE?
  14. GATE 2021 CS Q11 (1 mark, Multiple choice) – Suppose that L 1 is a regular language and L 2 is a context-free language. Which one of the following languages is NOT necessarily context-free?
  15. GATE 2020 CS Q18 (1 mark, Multiple choice) – Consider the following statements. I. If L 1 L 2 is regular, then both L 1 and L 2 must be regular. II. The class of regular languages is closed under…
  16. GATE 2020 CS Q20 (1 mark, Multiple choice) – Consider the language L=\an n 0\\anbn n 0\ and the following statements. I. L is deterministic context-free. II. L is context-free but not…
  17. GATE 2020 CS Q42 (2 marks, Multiple choice) – Consider the following languages. L 1=\wxyx w,x,y(0+1)+\ L 2=\xy x,y(a+b)*, x = y , x y\ Which one of the following is TRUE?