The GATE Grind

GATE 2025 CS (CS1) – Question 44

Theory of Computation · Regular and Context-Free Languages, Pumping Lemma · 2 marks · Multiple choice

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

$L_1 = \{ \alpha\beta\alpha \mid \alpha \in \{a,b\}^+ \text{ AND } \beta \in \{a,b\}^+ \}$
$L_2 = \{ \alpha\beta\alpha \mid \alpha \in \{a\}^+ \text{ AND } \beta \in \{a,b\}^+ \}$

Which ONE of the following statements is CORRECT?

  1. Both $L_1$ and $L_2$ are regular languages.
  2. $L_1$ is a regular language but $L_2$ is not a regular language.
  3. $L_1$ is not a regular language but $L_2$ is a regular language.
  4. Neither $L_1$ nor $L_2$ is a regular language.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $L_1$ is not a regular language but $L_2$ is a regular language.

Explanation

**$L_2=\{\alpha\beta\alpha\mid\alpha\in a^+,\ \beta\in\{a,b\}^+\}$ is regular.** Every string of $L_2$ starts with `a`, ends with `a` and has length $\ge3$. Conversely any such string $a\,u\,a$ with $|u|\ge1$ is in $L_2$ (take $\alpha=a,\ \beta=u$). So $L_2=a(a+b)^+a$.

**$L_1=\{\alpha\beta\alpha\mid\alpha,\beta\in\{a,b\}^+\}$ is NOT regular.** Here $\alpha$ may be longer than one symbol and must have the same value at the start and at the end, which lets us compare unbounded blocks. Intersect $L_1$ with the regular language $R=ab^*aab^*$ and take $w=ab^m\,aa\,b^n$.

So $L_1\cap R=\{ab^m aab^n\mid m\ge n\}$, which is not regular (pumping lemma on the $b^m$ block). Since regular languages are closed under intersection, $L_1$ is not regular.

$L_1$ is not regular and $L_2$ is regular: option (C).

More Regular and Context-Free Languages, Pumping Lemma questions

All Regular and Context-Free Languages, Pumping Lemma questions →