GATE CS 2019 Q.17 (CS Q.7): Regular Expressions, Finite Automata and Regular Languages

If $L$ is a regular language over $\Sigma = \{a, b\}$ , which one of the following languages is NOT regular?

$L \cdot L^R = \{xy \mid x \in L, y^R \in L\}$

$\{ww^R \mid w \in L\}$

$\text{Prefix}(L) = \{x \in \Sigma^* \mid \exists y \in \Sigma^* \text{ such that } xy \in L\}$

$\text{Suffix}(L) = \{y \in \Sigma^* \mid \exists x \in \Sigma^* \text{ such that } xy \in L\}$

Official answer and solution

Solution

Check standard closure properties of regular languages under concatenation, reversal, prefix, and palindromic construction.

Let $L$ be an arbitrary regular language over $\Sigma = \{a, b\}$ :

Option A: $L^R$ is regular (closure under reversal), and $L \cdot L^R$ is regular (closure under concatenation).
Option B: Let $L = (a + b)^*$ , which is regular. Then $\{ww^R \mid w \in L\} = \{ww^R \mid w \in \{a, b\}^*\}$ , which is the classic language of even-length palindromes. This language is well known to be non-regular (requires an unbounded stack to match symbols in reverse order). Hence, $\{ww^R \mid w \in L\}$ is NOT necessarily regular.
Option C: Regular languages are closed under the prefix operation $\text{Prefix}(L)$ .
Option D: Regular languages are closed under the suffix operation $\text{Suffix}(L)$ .

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.