L regular ⇔ finite number of distinguishable classes (= states of the minimal DFA)
What GATE asks from this
Question types seen repeatedly in past papers. More stars means more frequent.
★★★
Is this language regular / context-free?
Classify languages such as aⁿbⁿ, ww, aⁿbᵐ with conditions, using the pumping lemma or closure.
★★★
Closure-property true/false statements
Union, intersection, complement, reversal, infinite union, subsets of regular languages.
★★★
Which regular expression matches the language/DFA?
Test candidate regexes on short strings; spot equivalent ones using identities.
★★★
Minimal states / equivalence
Number of states in the minimal DFA of a regex-defined language.
Ratings are approximate, based on recurring patterns in past GATE CSE papers.
Previous year questions
14 real questions from the official GATE CSE papers (2012 to 2025), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.
14 questions · 0 correct of 0 attempted · marks 0 / 19
Year:
GATE 2025 CS1 · Q44MCQ2 marks
Consider the following two languages over the alphabet {a, b}: L1 = { αβα | α ∈ {a, b}+ AND β ∈ {a, b}+ } and L2 = { αβα | α ∈ {a}+ AND β ∈ {a, b}+ }. Which ONE of the following statements is CORRECT?
GATE 2025 CS2 · Q52MSQ2 marks
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 language(s)?
One or more options may be correct. Select all that apply, then submit.
GATE 2024 CS1 · Q23MSQ1 mark
Let L1, L2 be two regular languages and L3 a language which is not regular. Which of the following statements is/are always TRUE?
One or more options may be correct. Select all that apply, then submit.
GATE 2024 CS1 · Q61NAT2 marks
Consider the following two regular expressions over the alphabet {0,1}: r = 0* + 1*, s = 01* + 10*. The total number of strings of length less than or equal to 5, which are neither in r nor in s, is ______.
GATE 2024 CS2 · Q62NAT2 marks
Let L1 be the language represented by the regular expression b*ab*(ab*ab*)* and L2 = { w ∈ (a + b)* | |w| ≤ 4 }, where |w| denotes the length of string w. The number of strings in L2 which are also in L1 is ______.
GATE 2022 · Q47MSQ2 marks
Consider the following languages: L1 = { an w an | w ∈ {a, b}* } and L2 = { w x wR | w, x ∈ {a, b}*, |w|, |x| > 0 }. Note that wR is the reversal of the string w. Which of the following is/are TRUE?
One or more options may be correct. Select all that apply, then submit.
GATE 2020 · Q7MCQ1 mark
Which one of the following regular expressions represents the set of all binary strings with an odd number of 1's?
GATE 2020 · Q8MCQ1 mark
Consider the following statements. I. If L1 ∪ L2 is regular, then both L1 and L2 must be regular. II. The class of regular languages is closed under infinite union. Which of the above statements is/are TRUE?
GATE 2019 Set 2 · Q7MCQ1 mark
If L is a regular language over Σ = {a, b}, which one of the following languages is NOT regular?
GATE 2019 Set 2 · Q15MCQ1 mark
For Σ = {a, b}, let us consider the regular language L = { x | x = a2+3k or x = b10+12k, k ≥ 0 }. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for L?
GATE 2016 Set 1 · Q18MCQ1 mark
Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0s and two consecutive 1s?
GATE 2014 Set 1 · Q15MCQ1 mark
Which one of the following is TRUE?
GATE 2013 Code A · Q8MCQ1 mark
Consider the languages L1 = Φ and L2 = {a}. Which one of the following represents L1 L2* ∪ L1*?
GATE 2012 Code A · Q25MCQ1 mark
Given the language L = {ab, aa, baa}, which of the following strings are in L*? 1) abaabaaabaa 2) aaaabaaaa 3) baaaaabaaaab 4) baaaaabaa
Common traps
The class of regular languages is closed under finite union but not infinite union.
A non-regular language can be a subset of a regular one (aⁿbⁿ ⊂ a*b*).
Pumping lemma is a one-way test: failing it proves non-regular, passing it proves nothing.
In the pumping proof you must handle every legal split, with |xy| ≤ p.