GATE CS 2025 Set 1 — Question 44

Step 1: Analyze $L_2 = \{ \alpha \beta \alpha \mid \alpha \in \{a\}^+, \beta \in \{a, b\}^+ \}$.
Since $\alpha \in \{a\}^+$, we can write $\alpha = a^n$ for some $n \ge 1$. Thus $L_2 = \{ a^n \beta a^n \mid n \ge 1, \beta \in \{a, b\}^+ \}$.
Notice that any string in $L_2$ must start and end with 'a' and have length at least 3 (since $|\alpha| \ge 1$ and $|\beta| \ge 1$, $|w| = 2|\alpha| + |\beta| \ge 3$).
Conversely, any string $w$ that starts and ends with 'a' and has length $\ge 3$ can be written as $w = a \gamma a$ where $|\gamma| \ge 1$. By choosing $n=1$, $\alpha=a$, and $\beta=\gamma$, we see that $w \in L_2$.
Therefore, $L_2 = a \{a, b\}^+ a$, which is a regular language.Step 2: Analyze $L_1 = \{ \alpha \beta \alpha \mid \alpha, \beta \in \{a, b\}^+ \}$.
This is the set of strings that have a non-overlapping border. Consider the intersection of $L_1$ with the regular language $R = a b^+ a b^+$.
A string $w = a b^i a b^j \in R$ is in $L_1$ if and only if it has a non-overlapping border $\alpha$. Since $\alpha$ must be a prefix and a suffix starting with 'a', the only possible borders are of the form $a b^k$. For $a b^k$ to be a prefix, $k \le i$. For it to be a suffix, $k \le j$. For it to be non-overlapping, $2(k+1) < |w|$.
It can be shown that $a b^i a b^j \in L_1$ if and only if $j \le i$. The language $\{ a b^i a b^j \mid i \ge j \ge 1 \}$ is not regular. Since the intersection of $L_1$ with a regular language is not regular, $L_1$ itself is not regular.Conclusion: $L_1$ is not regular, but $L_2$ is regular.