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.
- GATE 2007 CS Q7 – Which is TRUE?
- GATE 2007 CS Q31 – Which language is regular? Here wᴿ denotes reversal and + means nonempty strings.
- GATE 2008 CS Q9 – Which statement is true of \ap p is prime\?
- GATE 2008 CS Q53 – 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\*\.
- GATE 2009 CS Q40 – 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
- GATE 2015 CS (CS2) Q46 – 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\.
- GATE 2011 CS Q34 – 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?
- GATE 2011 CS Q36 – 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?
- GATE 2013 CS Q42 – L 1=\0p1q0r:p,q,r0\ and L 2=\0p1q0r:p,q,r0,p r\. Which statement is false?
- GATE 2017 CS (CS2) Q14 – 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…
- GATE 2017 CS (CS2) Q50 – 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…
- GATE 2016 CS (CS2) Q27 – 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?
- GATE 2016 CS (CS2) Q28 – 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…
- GATE 2016 CS (CS2) Q53 – L 1=\anbmcn+m:m,n1\ and L 2=\anbnc2n:n1\. Which holds?
- GATE 2014 CS (CS2) Q25 – 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?
- GATE 2014 CS (CS2) Q46 – 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…
- GATE 2014 CS (CS1) Q25 – Which one of the following is TRUE?
- GATE 2017 CS (CS1) Q48 – 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…
- GATE 2019 CS Q17 – If L is a regular language over = a,b , which one of the following languages is NOT regular?
- GATE 2019 CS Q25 – 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…
- GATE 2025 CS (CS2) Q24 – Which ONE of the following languages is accepted by a deterministic pushdown automaton?
- GATE 2025 CS (CS2) Q30 – 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…
- GATE 2025 CS (CS2) Q52 – 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…
- GATE 2025 CS (CS1) Q44 – 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…
- GATE 2025 CS (CS1) Q45 – 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\…
- GATE 2024 CS (CS1) Q23 – 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?
- GATE 2023 CS Q24 – Which of the following statements is/are CORRECT?
- GATE 2022 CS Q23 – Which of the following statements is/are TRUE?
- GATE 2022 CS Q47 – 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…
- GATE 2022 CS Q48 – 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?
- GATE 2021 CS (CS1) Q11 – 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?
- GATE 2020 CS Q18 – 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…
- GATE 2020 CS Q20 – 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…
- GATE 2020 CS Q42 – 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?