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: (A) Both $L_1$ and $L_2$ are regular languages.

Explanation

L1 is the set of strings of length ≥3 that start and end with the same symbol (take α as one letter), which is regular. L2 is a(a+b)^+a, which is regular.