GATE 2025 CS1 Q.44: solution and answer

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.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

$L_{1}$ is not regular, but $L_{2} = a (a + b)^{+} a$ is regular, so the answer is (C).

Official answer: CSource: Official answer key, GATE 2025 CS1 (IIT Roorkee)

$L_{2}$ is regular. Every string of $L_{2}$ has the form $a^{i} β a^{i}$ with $i \geq 1$ and $β \neq = ε$ , so it starts with $a$ , ends with $a$ and has length at least $3$ . Conversely, any string $a x a$ with $x \in {a, b}^{+}$ is in $L_{2}$ : take $α = a$ and $β = x$ . Hence $L_{2} = a (a + b)^{+} a$ , which is regular.
$L_{1}$ is not regular. A string $w$ is in $L_{1}$ exactly when it has a nonempty border $α$ (a string that is both a prefix and a suffix of $w$ ) with $2∣ α ∣ < ∣ w ∣$ , so that a nonempty $β$ fits between the two copies. We use the Myhill-Nerode theorem on the strings $x_{i} = a^{i} b$ for $i \geq 1$ .
Take $1 \leq j < i$ and the suffix $z = b a^{j} b$ . Then $x_{j} z = a^{j} b b a^{j} b = α β α$ with $α = a^{j} b$ and $β = b$ , so $x_{j} z \in L_{1}$ .
Now consider $x_{i} z = a^{i} b b a^{j} b$ , of length $i + j + 3$ . It starts with $a$ , so any border starts with $a$ and ends with $b$ . A suffix starting with $a$ is either $a^{k} b$ with $1 \leq k \leq j$ (taken from the last block), or $a^{m} b b a^{j} b$ with $1 \leq m \leq i$ (taken from the first block).
If the border is $a^{k} b$ , the prefix of the same length must be $a^{i} b$ (the word begins $a^{i} b$ ), which forces $k = i$ . But $k \leq j < i$ , a contradiction. If the border is $a^{m} b b a^{j} b$ , its prefix starts with $a^{m} b$ , which forces $m = i$ , and then the border is the whole word, which is not a proper border. So $x_{i} z$ has no valid border and $x_{i} z \in / L_{1}$ .
Thus for every pair $j < i$ the suffix $b a^{j} b$ separates $x_{j}$ from $x_{i}$ . The strings $a^{i} b$ ( $i \geq 1$ ) are pairwise distinguishable, so $L_{1}$ has infinitely many Myhill-Nerode classes and is not regular.
Therefore $L_{1}$ is not regular and $L_{2}$ is regular, which is option (C).

KEY IDEA

$L_{2}$ collapses to the regular language $a (a + b)^{+} a$ because the single letter $a$ can always serve as $α$ . In $L_{1}$ , $α$ can be any nonempty word, so the language demands a long matching border, and Myhill-Nerode on $a^{i} b$ shows it is not regular.

WATCH OUT FOR

Seeing the same $α$ at both ends and assuming both languages need unbounded memory, or assuming both are regular because the first and last letters match. In $L_{1}$ a border can start and end with different letters, for example $abbab$ with $α = ab$ , so $L_{1}$ is not just "first letter equals last letter". Also, the separating suffix must be chosen from the smaller index: $b a^{i} b$ fails for $j < i$ because $a^{j} b$ is then also a border of $x_{j} z_{i}$ .

From the GATE 2025 CS1 paper. Every question of this paper · Download the full paper · All 5 Regular languages questions, with notes

GATE 2025 CS1 Q.44: solution and answer

Answer and solution

More Regular languages questions