The GATE Grind

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

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

34 questions worth 50 marks in all (18 1-mark, 16 2-mark). Asked between 2007 and 2025, so you can see how the topic has been tested over time.

  1. GATE 2007 CS Q7 (1 mark, Multiple choice) – Which is TRUE?
  2. GATE 2007 CS Q31 (2 marks, Multiple choice) – Which language is regular? Here wᴿ denotes reversal and + means nonempty strings.
  3. GATE 2008 CS Q9 (1 mark, Multiple choice) – Which statement is true of \ap p is prime\?
  4. GATE 2008 CS Q53 (2 marks, Multiple choice) – Which are regular sets? I. \an b2m n0,m0\; II. \an bm n=2m\; III. \an bm n m\; IV. \xcy x,y\a,b\*\.
  5. GATE 2009 CS Q40 (2 marks, Multiple choice) – Let L=L 1 L 2, where L 1=\am bm c an bn m,n0\ and L 2=\ai bj ck i,j,k0\. Then L is
  6. GATE 2015 CS (CS2) Q46 (2 marks, Multiple choice) – Which languages are regular? L 1=\wxwR:w,x\a,b\*,\ w , x >0\; L 2=\anbm:m n,\ m,n0\; L 3=\apbqcr:p,q,r0\.
  7. GATE 2011 CS Q34 (1 mark, Multiple choice) – P is regular and Q is context-free with Q⊆P, e.g. P=p*q* and Q=pⁿqⁿ:n∈N. Which is always regular?
  8. GATE 2011 CS Q36 (2 marks, Multiple choice) – L 1=\0p1q:p,q N\, L 2=\0p1q:p,q N,p=q\, L 3=\0p1q0r:p,q,r N,p=q=r\. Which is NOT true?
  9. GATE 2013 CS Q42 (2 marks, Multiple choice) – L 1=\0p1q0r:p,q,r0\ and L 2=\0p1q0r:p,q,r0,p r\. Which statement is false?
  10. GATE 2017 CS (CS2) Q14 (1 mark, Multiple choice) – L₁,L₂ are context-free and R is regular. Which are correct? I: L₁∪L₂ is context-free. II: L 1 is context-free. III: L₁−R is context-free. IV: L₁∩L₂ is…
  11. GATE 2017 CS (CS2) Q50 (2 marks, Multiple choice) – L₁=aᵖ:p prime, L 2=\anbmc2m:n,m0\, L 3=\anbnc2n:n0\, L₄=aⁿbⁿ:n≥1. Which hold? I: L₁ context-free but not regular. II: L₂ not context-free. III: L₃ not…
  12. GATE 2016 CS (CS2) Q27 (1 mark, Multiple choice) – S 1 aS 1b generates L₁ and S 2 abS 2 generates L₂. P says L₁ is regular; Q says L₂ is regular. Which is true?
  13. GATE 2016 CS (CS2) Q28 (1 mark, Multiple choice) – L₁ is regular, L₂ context-free, L₃ recursive and L₄ recursively enumerable. Which hold? I: L 3 L 4 is recursively enumerable. II: L 2 L 3 is…
  14. GATE 2016 CS (CS2) Q53 (2 marks, Multiple choice) – L 1=\anbmcn+m:m,n1\ and L 2=\anbnc2n:n1\. Which holds?
  15. GATE 2014 CS (CS2) Q25 (1 mark, Multiple choice) – Let L 1=\an:n0\ and L 2=\bn:n0\. I: L 1L 2 is regular. II: L 1L 2=\anbn:n0\. Which is correct?
  16. GATE 2014 CS (CS2) Q46 (2 marks, Multiple choice) – L₁ consists of binary strings with at least as many occurrences of 110 as of 011. L₂ consists of binary strings with at least as many occurrences of…
  17. GATE 2014 CS (CS1) Q25 (1 mark, Multiple choice) – Which one of the following is TRUE?
  18. GATE 2017 CS (CS1) 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…
  19. 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?
  20. 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…
  21. GATE 2025 CS (CS2) Q24 (1 mark, Multiple choice) – Which ONE of the following languages is accepted by a deterministic pushdown automaton?
  22. 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…
  23. 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…
  24. 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…
  25. 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\…
  26. 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?
  27. GATE 2023 CS Q24 (1 mark, Multiple select) – Which of the following statements is/are CORRECT?
  28. GATE 2022 CS Q23 (1 mark, Multiple select) – Which of the following statements is/are TRUE?
  29. 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…
  30. 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?
  31. GATE 2021 CS (CS1) 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?
  32. 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…
  33. 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…
  34. 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?