GATE CS

Regular languages

Closure properties and the pumping lemma

Regular languages are closed under many operations, so you can often prove a language regular or non-regular without building a machine. The decision properties make every basic question about a regular language answerable by an algorithm. The pumping lemma and the Myhill-Nerode theorem are the two standard tools for proving non-regularity, and Myhill-Nerode also counts the states of the minimal DFA.

5 previous-year questions · 5 solved · 6 practice questions

1. Closure properties

Conventions used here: $Σ$ is the input alphabet, $ε$ the empty string, $∣ w ∣$ the length of $w$ , $#_{a} (w)$ the number of occurrences of the symbol $a$ in $w$ , and $L^{c} = \overline{L} = Σ^{*} ∖ L$ the complement with respect to $Σ^{*}$ . A DFA's transition function is total unless stated otherwise. A class is closed under an operation if applying the operation to members of the class always gives a member of the class.

Operation	Regular languages closed?	Why (construction)
Union $L_{1} \cup L_{2}$	Yes	New start state with $ε$ -moves to both start states, or the product construction
Intersection $L_{1} \cap L_{2}$	Yes	Product construction, accepting when both components accept
Finite unions and intersections $L_{1} \cup \dots \cup L_{k}$ , $L_{1} \cap \dots \cap L_{k}$	Yes	Apply the two-language case $k - 1$ times
Complement $L^{c}$	Yes	Take a total DFA and swap accepting and non-accepting states
Difference $L_{1} - L_{2}$	Yes	$L_{1} \cap L_{2}^{c}$
Concatenation $L_{1} L_{2}$	Yes	$ε$ -moves from the accepting states of the first NFA to the start of the second; only the second NFA's accepting states accept
Kleene star $L^{*}$	Yes	New start state that is accepting, with an $ε$ -move to the old start; $ε$ -moves from the old accepting states back to the old start
Reversal $L^{R}$	Yes	Reverse every arrow, make the old start the only accepting state, add a new start with $ε$ -moves to the old accepting states
Homomorphism $h (L)$	Yes	Replace each symbol in a regular expression for $L$ by its image
Substitution of a regular language for each symbol	Yes	Replace each symbol in a regular expression for $L$ by a regular expression for its language
Inverse homomorphism $h^{- 1} (L)$	Yes	A DFA for $L$ reads the whole string $h (a)$ in one step
Prefixes ${x : x y \in L for some y}$ ; right quotient $L / M = {x : x y \in L for some y \in M}$ , any language $M$	Yes	Keep the DFA; make a state accepting if some $y$ (some $y \in M$ for the quotient) leads from it to an accepting state. The new accepting set always exists; it can be computed when $M$ is regular
Suffixes ${y : x y \in L for some x}$	Yes	New start state with $ε$ -moves to every state reachable from the old start
Union of infinitely many regular languages	No, in general	${a^{n} b^{n} : n \geq 0}$ is the union of the singletons ${a^{n} b^{n}}$ over $n \geq 0$ , each finite and so regular. Infinite intersections fail too: ${a^{n} b^{n}}$ is the intersection of the regular languages $Σ^{*} ∖ {w}$ over all $w \in / {a^{n} b^{n}}$
Taking a subset or a superset	No, in general	Subset: ${a^{n} b^{n}} \subseteq a^{} b^{}$ , where $a^{} b^{}$ is regular and ${a^{n} b^{n}}$ is not. Superset: ${a^{n} b^{n}} \supseteq \emptyset$ , where $\emptyset$ is regular and ${a^{n} b^{n}}$ is not

COMPLEMENT OF A REGULAR LANGUAGE

\overline{L} = Σ^{*} ∖ L : Q^{'} = Q, F^{'} = Q ∖ F

Applies to a total DFA only. If some transitions are missing, first add a dead (trap) state and send every missing transition to it. The complement DFA has the same states, so the minimal total DFAs of $L$ and $L^{c}$ have the same number of states. Swapping accepting states in an NFA does not complement it: convert the NFA to a DFA first (the subset construction can need up to $2^{n}$ states for an $n$ -state NFA).

PRODUCT CONSTRUCTION

δ ((p, q), a) = (δ_{1} (p, a), δ_{2} (q, a)), start (s_{1}, s_{2})

For total DFAs with $m$ and $n$ states, the product has $mn$ states. A pair is accepting when both components accept for intersection, when either accepts for union, and when the first accepts and the second does not for difference.

INVERSE HOMOMORPHISM

δ^{'} (q, a) = \hat{δ} (q, h (a))

Here $\hat{δ}$ is the extended transition function on strings, with $\hat{δ} (q, ε) = q$ . The new DFA has the same states, start state and accepting states as the DFA for $L$ , and it accepts $h^{- 1} (L) = {w : h (w) \in L}$ .

EXAM TIP

Being a subset or superset of a regular language tells you nothing. A non-regular language can sit inside a regular one, and a regular language can sit inside a non-regular one. Only the operations in the closure table let you conclude regularity.

2. Using closure to decide regularity

Closure gives two proof patterns. To show a language is regular, build it from known regular languages with closed operations. To show it is non-regular, assume it is regular, apply closed operations to reach a language already known to be non-regular, and conclude by contradiction.

Showing non-regularity by closure

Assume $L$ is regular.
Apply closed operations that involve only $L$ and regular languages: intersect with a regular language such as $a^{*} b^{*}$ , take a complement, or apply a homomorphism or an inverse homomorphism. Combining $L$ with a non-regular language proves nothing.
If the result is a known non-regular language such as ${a^{n} b^{n} : n \geq 0}$ , then $L$ is not regular.

WORKED EXAMPLE

Let $L = {w \in {a, b}^{*} : #_{a} (w) = #_{b} (w)}$ . Is $L$ regular?

Solution

Suppose $L$ were regular.
$a^{*} b^{*}$ is regular, so $L \cap a^{*} b^{*}$ would be regular.
A string $a^{i} b^{j}$ has equal numbers of $a$ and $b$ exactly when $i = j$ , so $L \cap a^{*} b^{*} = {a^{n} b^{n} : n \geq 0}$ .
That language is not regular, a contradiction.

Answer: $L$ is not regular.

EXAM TIP

Do not claim a language is regular just because its strings look simple or because it is a subset of $a^{*} b^{*}$ . Comparing two counts with no fixed bound is a warning sign of non-regularity, but it is not a proof. The language ${w \in {a, b}^{*} : the number of ab equals the number of ba}$ looks like such a comparison and is regular (Section 6). Prove each case with closure, the pumping lemma or Myhill-Nerode.

3. Decision properties

When a regular language is given by a DFA, an NFA or a regular expression (converted to a DFA first if needed), an algorithm decides each question below.

Question	Test
Emptiness: is $L = \emptyset$ ?	Search the transition graph from the start state. $L$ is empty exactly when no accepting state is reachable
Finiteness: is $L$ finite?	$L$ is infinite exactly when some cycle lies on a path from the start state to an accepting state (only states that are reachable and can reach an accepting state count). Equivalently, for an $n$ -state DFA, $L$ is infinite exactly when it contains a string $w$ with $n \leq ∣ w ∣ < 2 n$
Membership: is $w \in L$ ?	Run the DFA on $w$ for $∣ w ∣$ steps
Universality: is $L = Σ^{*}$ ?	Check that the complement is empty
Equivalence: is $L_{1} = L_{2}$ ?	Check that $(L_{1} - L_{2}) \cup (L_{2} - L_{1})$ is empty, or minimise both DFAs and compare them up to renaming of states
Subset: is $L_{1} \subseteq L_{2}$ ?	Check that $L_{1} \cap L_{2}^{c}$ is empty

EXAM TIP

All of these are decidable for regular languages. Do not carry the answers over to context-free languages. For CFLs, emptiness, finiteness and membership are decidable, but universality and equivalence are not.

4. The pumping lemma

PUMPING LEMMA FOR REGULAR LANGUAGES

L regular \Rightarrow \exists p \geq 1 \forall w \in L with ∣ w ∣ \geq p \exists x, y, z : w = x y z, ∣ x y ∣ \leq p, ∣ y ∣ \geq 1, and x y^{i} z \in L \forall i \geq 0

The implication runs one way only. A language can satisfy the conditions and still be non-regular, so the lemma can prove non-regularity but never regularity. For example, ${a^{i} b^{j} c^{k} : i = 0 or j = k}$ satisfies the lemma with $p = 1$ (pump the first symbol), yet it is not regular: its intersection with $a b^{*} c^{*}$ is ${a b^{n} c^{n} : n \geq 0}$ . The pumping length $p$ can be taken as the number of states of any DFA for $L$ .

Here is why the lemma holds. Take a DFA with $p$ states. Reading the first $p$ symbols of $w$ , it visits $p + 1$ states, so some state repeats; this gives $∣ x y ∣ \leq p$ . The part $y$ read between the two visits is a loop. Repeating the loop any number of times, or deleting it ( $i = 0$ ), leaves the DFA in the same state afterwards, so acceptance does not change.

Proving non-regularity: a game against an adversary

Assume $L$ is regular. The adversary then supplies a pumping length $p$ ; you do not choose $p$ .
You choose a string $w \in L$ with $∣ w ∣ \geq p$ , written in terms of $p$ (for example $a^{p} b^{p}$ ).
The adversary splits $w = x y z$ with $∣ x y ∣ \leq p$ and $∣ y ∣ \geq 1$ . Your argument must handle every such split.
You choose $i \geq 0$ (usually $0$ or $2$ ) with $x y^{i} z \in / L$ .
This contradicts the lemma, so $L$ is not regular.

WORKED EXAMPLE

Show that $L = {0^{n} 1^{2 n} : n \geq 0}$ is not regular.

Solution

Assume $L$ is regular with pumping length $p$ .
Choose $w = 0^{p} 1^{2 p} \in L$ ; $∣ w ∣ = 3 p \geq p$ .
Since $∣ x y ∣ \leq p$ and the first $p$ symbols are all $0$ s, $y = 0^{k}$ with $k \geq 1$ .
Take $i = 2$ : $x y^{2} z = 0^{p + k} 1^{2 p}$ , which has $p + k$ zeros and $2 p$ ones.
Since $2 (p + k) \neq = 2 p$ , this string is not in $L$ , a contradiction.

Answer: $L$ is not regular.

EXAM TIP

Choose $w$ so that $∣ x y ∣ \leq p$ forces $y$ into one block of symbols. A bad choice lets the adversary find a split you cannot beat. For ${w w : w \in {a, b}^{*}}$ , the string $a^{2 p}$ is a bad choice: with $y = aa$ , every $x y^{i} z$ is an even-length run of $a$ s and stays in the language. The string $a^{p} b a^{p} b$ works. Strings such as $a^{p} b^{p}$ and $0^{p} 1^{2 p}$ are standard good choices.

EXAM TIP

The lemma only talks about strings at least $p$ long. Finite languages are always regular, and they satisfy the lemma vacuously when $p$ is larger than their longest string, so the lemma is never applied to them.

5. Myhill-Nerode theorem

Two strings $x, y \in Σ^{*}$ are equivalent with respect to $L$ , written $x \sim_{L} y$ , if for every string $z$ , $x z \in L$ exactly when $y z \in L$ . This is an equivalence relation. A string $z$ that puts one of $x z, y z$ in $L$ and the other outside $L$ is a distinguishing suffix.

MYHILL-NERODE THEOREM

L regular ⟺ \sim_{L} has finitely many equivalence classes

Unlike the pumping lemma, this is an iff. The number of classes equals the number of states of the minimal total DFA for $L$ , counting the dead state if the minimal total DFA has one.

Counting classes or showing non-regularity

To count classes, find a set of strings that are pairwise distinguishable and show that every string is equivalent to one of them. The size of the set is the size of the minimal DFA.
To prove non-regularity, exhibit infinitely many pairwise distinguishable strings. For ${a^{n} b^{n}}$ , the strings $a, a^{2}, a^{3}, \dots$ work: the suffix $b^{i}$ separates $a^{i}$ from $a^{j}$ when $i \neq = j$ .
The minimal total DFA for $L$ is unique up to renaming of states.

Minimising a DFA (table filling)

Make the DFA total and remove the states that cannot be reached from the start state.
Mark every pair ${p, q}$ where exactly one of $p, q$ is accepting.
Repeat until nothing changes: mark ${p, q}$ if for some symbol $a$ the pair ${δ (p, a), δ (q, a)}$ is marked.
Unmarked pairs are equivalent. Merging each group of equivalent states gives the minimal DFA.

WORKED EXAMPLE

Let $L = {w \in {0, 1}^{*} : the third symbol from the right end of w is 1}$ . How many states does the minimal total DFA for $L$ have?

Solution

For any suffix $z$ with $∣ z ∣ \geq 3$ , whether $w z \in L$ depends only on $z$ . For $∣ z ∣ \leq 2$ , it depends on $z$ and the last $3 - ∣ z ∣$ symbols of $w$ . So the class of $w$ is fixed by the last three symbols of $w$ .
Treat a string shorter than three symbols as padded with $0$ s on the left. A missing position is never a $1$ , so a short string behaves exactly like its padded version for every suffix (for example $ε \sim_{L} 000$ and $1 \sim_{L} 001$ ). That leaves at most $2^{3} = 8$ classes, one for each triple of last symbols.
Two different triples differ at some position. Append a suffix of length $0$ , $1$ or $2$ so that this position becomes the third from the right. Then exactly one of the two strings is in $L$ , so all 8 triples are pairwise distinguishable.
Each triple is reached by the string made of those three symbols, and every string falls into one of the 8 classes, so there are exactly 8 classes.

Answer: 8

6. Is this language regular? Quick reference

Language	Regular?	Reason
${a^{n} b^{n} : n \geq 0}$	No	Must match two counts with no bound; pumping lemma on $a^{p} b^{p}$ , or Myhill-Nerode
${w w : w \in {a, b}^{*}}$	No	Pump $a^{p} b a^{p} b$ ; $y$ lies in the first block of $a$ s. (Over a one-letter alphabet it is $(aa)^{*}$ , which is regular)
${w w^{R} : w \in {a, b}^{*}}$	No	Pump $a^{p} bb a^{p}$ ; $y$ lies in the first block of $a$ s, and $x y^{2} z$ is no longer an even-length palindrome. (Over a one-letter alphabet it is $(aa)^{*}$ , which is regular)
${w \in {a, b}^{*} : #_{a} (w) = #_{b} (w)}$	No	Intersection with $a^{} b^{}$ gives ${a^{n} b^{n}}$
${a^{n^{2}} : n \geq 0}$ or ${a^{q} : q prime}$	No	In an infinite one-letter regular language the lengths are eventually periodic, so the gaps between members are bounded. Here the gaps grow without bound
${a^{n} b^{m} : n + m even}$	Yes	$(aa)^{} (bb)^{} + a (aa)^{} b (bb)^{}$
${w : #_{a} (w) mod 3 = 1}$	Yes	Three states remember the count modulo 3
${a^{n} b^{m} : n \neq = m}$	No	Its complement intersected with $a^{} b^{}$ is ${a^{n} b^{n}}$
${a^{n} b^{m} : n, m \geq 0}$	Yes	The regular expression $a^{} b^{}$
${a^{n} b^{n} : 0 \leq n \leq 100}$	Yes	Finite (101 strings)
${w \in {a, b}^{*} : the number of occurrences of ab equals the number of occurrences of ba}$	Yes	Over ${a, b}$ the two counts differ by at most 1, and they are equal exactly when $w = ε$ or the first and last symbols of $w$ are equal
${w x w^{R} : w, x \in {a, b}^{+}}$	Yes	It equals $a (a + b)^{+} a + b (a + b)^{+} b$ : take $w$ to be the first symbol
Any finite language	Yes	A finite union of single strings

EXAM TIP

Matching two quantities against each other with no fixed bound is a warning sign of non-regularity. Counting modulo a constant, or comparing a count with a fixed number, is regular. Always check small cases and look for a simpler description: ${w x w^{R}}$ and the equal- $ab$ -and- $ba$ language both look non-regular and are regular.

EXAM TIP

Regularity has nothing to do with being infinite or being easy to describe. A language is regular exactly when it has a finite automaton, exactly when it has a regular expression, and exactly when it has finitely many Myhill-Nerode classes.

PREVIOUS-YEAR QUESTIONS

5 questions from the CS papers

Try each question first, then open the answer. We placed each question under a topic ourselves; the exam paper does not label topics.

See these papers in full: GATE CSE 2026 Set 1 · GATE CSE 2025 Set 1 · GATE CSE 2025 Set 2 · GATE CSE 2024 Set 1 · GATE CSE 2020

GATE 2026 CS1 Q.51

GATE 2026 · CS1Q.51 · 2 marks · MSQ

Let $L_{1}$ and $L_{2}$ be two languages over a finite alphabet, such that $L_{1} \cap L_{2}$ and $L_{2}$ are regular languages.

Which of the following statements is/are always true?

(A)
$L_{1}$ is regular
(B)
$L_{1} \cup L_{2}$ is regular
(C)
$\overline{L_{2}}$ is context-free
(D)
$L_{1}$ is context-free

Answer and solution

GATE 2026 CS1 Q.51: answer and solution

See the question in the paper

Tap to open full size

GATE 2026 CS1 Q.51: answer and solution

GATE 2025 CS1 Q.44

GATE 2025 · CS1Q.44 · 2 marks · MCQ

Consider the following two languages over the alphabet ${a, b}$ :

$L_{1} = {α β α ∣ α \in {a, b}^{+} AND β \in {a, b}^{+}}$

$L_{2} = {α β α ∣ α \in {a}^{+} AND β \in {a, b}^{+}}$

Which ONE of the following statements is CORRECT?

(A)
Both $L_{1}$ and $L_{2}$ are regular languages.
(B)
$L_{1}$ is a regular language but $L_{2}$ is not a regular language.
(C)
$L_{1}$ is not a regular language but $L_{2}$ is a regular language.
(D)
Neither $L_{1}$ nor $L_{2}$ is a regular language.

Answer and solution

GATE 2025 CS1 Q.44: answer and solution

See the question in the paper

Tap to open full size

GATE 2025 CS1 Q.44: answer and solution

GATE 2025 CS2 Q.52

GATE 2025 · CS2Q.52 · 2 marks · MSQ

Let $Σ = {a, b, c}$ . For $x \in Σ^{*}$ and $α \in Σ$ , let $#_{α} (x)$ denote the number of occurrences of $α$ in $x$ .

Which one or more of the following option(s) define(s) regular language(s)?

(A)
${a^{m} b^{n} ∣ m, n \geq 0}$
(B)
${a, b}^{*} \cap {a^{m} b^{n} c^{m - n} ∣ m \geq n \geq 0}$
(C)
${w ∣ w \in {a, b}^{*}, #_{a} (w) \equiv 2 (mod 7), and #_{b} (w) \equiv 3 (mod 9)}$
(D)
${w ∣ w \in {a, b}^{*}, #_{a} (w) \equiv 2 (mod 7), and #_{a} (w) = #_{b} (w)}$

Answer and solution

GATE 2025 CS2 Q.52: answer and solution

See the question in the paper

Tap to open full size

GATE 2025 CS2 Q.52: answer and solution

GATE 2024 CS1 Q.23

GATE 2024 · CS1Q.23 · 1 mark · MSQ

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?

(A)
$L_{1} = L_{2}$ if and only if $L_{1} \cap \overline{L_{2}} = ϕ$
(B)
$L_{1} \cup L_{3}$ is not regular
(C)
$\overline{L_{3}}$ is not regular
(D)
$\overline{L_{1}} \cup \overline{L_{2}}$ is regular

Answer and solution

GATE 2024 CS1 Q.23: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 CS1 Q.23: answer and solution

GATE 2020 CS Q.8

GATE 2020 · CSQ.8 · 1 mark · MCQ

Consider the following statements.
I. If $L_{1} \cup L_{2}$ is regular, then both $L_{1}$ and $L_{2}$ must be regular.
II. The class of regular languages is closed under infinite union.
Which of the above statements is/are TRUE?

(A)
I only
(B)
II only
(C)
Both I and II
(D)
Neither I nor II

Answer and solution

GATE 2020 CS Q.8: answer and solution

See the question in the paper

Tap to open full size

GATE 2020 CS Q.8: answer and solution

PRACTICE

6 questions to test yourself

PRACTICE 11 mark · MCQ

Which one of the following languages over ${a, b}$ is regular?

(A)
${a^{n} b^{n} : n \geq 0}$
(B)
${w : #_{a} (w) = #_{b} (w)}$
(C)
${a^{n} b^{m} : n + m is even}$
(D)
${a^{n^{2}} : n \geq 0}$

Answer and solution

Answer: (C)

A is the standard non-regular language: it must match $n$ $a$ s against $n$ $b$ s.
B intersected with $a^{*} b^{*}$ gives A, so B is not regular.
D has gaps between consecutive members that grow without bound, so it is not regular.
C needs $n$ and $m$ both even or both odd. The regular expression $(aa)^{*} (bb)^{*} + a (aa)^{*} b (bb)^{*}$ describes it, so C is regular.

PRACTICE 22 marks · MSQ

Over the alphabet $Σ = {a, b}$ , which of the following statements are TRUE?

(A)
Every subset of a regular language is regular.
(B)
If $L$ is regular and $h$ is a homomorphism, then $h (L)$ is regular.
(C)
If $L_{1}$ and $L_{2}$ are both non-regular, then $L_{1} \cup L_{2}$ is non-regular.
(D)
The complement of a regular language over $Σ$ is regular.

Answer and solution

Answer: (B), (D)

A is false: ${a^{n} b^{n}}$ is a subset of the regular language $Σ^{*}$ but is not regular.
B is true: regular languages are closed under homomorphism.
C is false: take $L_{1} = {a^{n} b^{n}}$ and $L_{2}$ its complement. $L_{2}$ is non-regular, since otherwise $L_{1} = L_{2}^{c}$ would be regular. The union is $Σ^{*}$ , which is regular.
D is true: swap the accepting and non-accepting states of a total DFA.

PRACTICE 31 mark · NAT

A total DFA $M_{1}$ has 5 states and a total DFA $M_{2}$ has 7 states, both over the same alphabet. The product construction builds a DFA for $L (M_{1}) \cap L (M_{2})$ that keeps every pair of states as a state, reachable or not. How many states does this DFA have?

Answer and solution

Answer: $35$

The product DFA has one state for each pair $(p, q)$ , where $p$ is a state of $M_{1}$ and $q$ a state of $M_{2}$ .
The count is $5 \times 7 = 35$ .

PRACTICE 42 marks · MCQ

Let $L = {0^{i} 1^{j} : i \neq = j, i, j \geq 0}$ , and let $\overline{L}$ be its complement with respect to ${0, 1}^{*}$ . Which statement is correct?

(A)
$L$ is regular because $L \subseteq 0^{*} 1^{*}$ and $0^{*} 1^{*}$ is regular.
(B)
$L$ is not regular, because if it were, $\overline{L} \cap 0^{*} 1^{*}$ would be a regular language equal to ${0^{n} 1^{n} : n \geq 0}$ .
(C)
$L$ is regular because it is an infinite language.
(D)
$L$ is not regular, because it fails the pumping lemma conditions only when $i = j$ .

Answer and solution

Answer: (B)

A is wrong: a subset of a regular language need not be regular.
C is wrong: being infinite says nothing about regularity.
Within $0^{*} 1^{*}$ , the strings not in $L$ are exactly those with $i = j$ , so $\overline{L} \cap 0^{*} 1^{*} = {0^{n} 1^{n} : n \geq 0}$ .
If $L$ were regular, its complement and that complement's intersection with $0^{*} 1^{*}$ would be regular. But ${0^{n} 1^{n}}$ is not regular, so $L$ is not regular, and B is correct.
D gives a false reason: the pumping lemma is about long strings of $L$ itself and says nothing about the strings with $i = j$ , which are not in $L$ .

PRACTICE 52 marks · MCQ

Let $L_{1} = {w x w^{R} : w, x \in {a, b}^{+}}$ and $L_{2} = {w w^{R} : w \in {a, b}^{+}}$ , where $w^{R}$ is the reverse of $w$ . Which statement is correct?

(A)
$L_{1}$ is regular and $L_{2}$ is not regular.
(B)
Both $L_{1}$ and $L_{2}$ are regular.
(C)
$L_{1}$ is not regular and $L_{2}$ is regular.
(D)
Neither $L_{1}$ nor $L_{2}$ is regular.

Answer and solution

Answer: (A)

Every string $w x w^{R}$ has length at least 3 and starts and ends with the first symbol of $w$ .
Conversely, any string $c u c$ with $c \in {a, b}$ and $u \in {a, b}^{+}$ is $w x w^{R}$ with $w = c$ and $x = u$ .
So $L_{1} = a (a + b)^{+} a + b (a + b)^{+} b$ , which is regular.
$L_{2}$ is the set of non-empty even-length palindromes. Pump $w = a^{p} bb a^{p}$ : $y = a^{k}$ with $k \geq 1$ lies in the first block, and $x y^{2} z = a^{p + k} bb a^{p}$ is not a palindrome, so $L_{2}$ is not regular.
Hence A.

PRACTICE 62 marks · NAT

Let $L = {w \in {0, 1}^{*} : #_{1} (w) \equiv 2 (mod 3) and ∣ w ∣ is even}$ . How many states does the minimal total DFA for $L$ have?

Answer and solution

Answer: $6$

Track the pair $(#_{1} (w) mod 3, ∣ w ∣ mod 2)$ . There are $3 \times 2 = 6$ pairs. A DFA with these pairs as states, start state $(0, 0)$ and the single accepting state $(2, 0)$ , accepts $L$ .
Reading $1$ adds $(1, 1)$ and reading $0$ adds $(0, 1)$ . Reading $1$ repeatedly from $(0, 0)$ visits $(1, 1), (2, 0), (0, 1), (1, 0), (2, 1), (0, 0)$ , so all 6 pairs are reachable.
A suffix $z$ moves every pair by the same amount, $(#_{1} (z) mod 3, ∣ z ∣ mod 2)$ , so two different pairs always end at two different pairs. Pick a suffix that takes the first pair to $(2, 0)$ : it takes the second pair somewhere else. So any two pairs are distinguishable.
No two states can be merged, so the minimal DFA has 6 states.

OFFICIAL GATE 2027 SYLLABUS WORDING

Copied from the GATE 2027 syllabus; see all 2027 syllabi.

GATE CS

Regular … languages, pumping lemma

Preparing in Kolkata? IAE Academy's course for GATE CSE.