GATE 2025 CS (CS1) – Question 44
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?
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$.
- If $m\ge n$: let $\alpha=ab^n$. Then $w=\alpha\cdot(b^{m-n}a)\cdot\alpha$ with a non-empty middle, so $w\in L_1$.
- If $m<n$: $\alpha$ must start with `a` and be both a prefix and a suffix. The suffixes of $w$ that start with `a` are $ab^n$, $aab^n$ and longer ones. The prefix of length $n+1$ is $ab^m$ followed by `a` or `b`, which cannot equal $ab^n$ when $m<n$. No valid $\alpha$ exists, so $w\notin L_1$.
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
- GATE 2025 CS (CS1) Q45
- GATE 2025 CS (CS2) Q24
- GATE 2025 CS (CS2) Q30
- GATE 2025 CS (CS2) Q52
- GATE 2024 CS (CS1) Q23
- GATE 2023 CS Q24
All Regular and Context-Free Languages, Pumping Lemma questions →