GATE CS 2019 Q7 — Regular and Context-free Languages

To determine which language is NOT guaranteed to be regular, let us analyze each option given that $L$ is a regular language over $\Sigma = \{a,b\}$:

• Option A: $L.L^R = \{xy \mid x \in L, y^R \in L\}$
  Since regular languages are closed under reversal, $L^R$ is regular. Regular languages are also closed under concatenation, so the concatenation $L.L^R$ is guaranteed to be regular.
• Option B: $\{ww^R \mid w \in L \}$
  This language requires a matching of the string $w$ with its reverse $w^R$, which generally requires a stack (memory) to keep track of the symbols in $w$.
  For example, if we choose the regular language $L = \Sigma^* = \{a,b\}^*$, then the language becomes $\{ww^R \mid w \in \{a,b\}^*\}$, which is the classic non-regular (but context-free) language of even-length palindromes. Thus, this language is not regular in general.
• Option C: $\text{Prefix}(L) = \{x \in \Sigma^* \mid \exists y \in \Sigma^* \text{ such that } xy \in L\}$
  Regular languages are closed under the prefix operation. If $L$ is recognized by a DFA $M$, we can construct a DFA for $\text{Prefix}(L)$ by making any state in $M$ from which a final state is reachable an accepting state.
• Option D: $\text{Suffix}(L) = \{y \in \Sigma^* \mid \exists x \in \Sigma^* \text{ such that } xy \in L\}$
  Regular languages are closed under the suffix operation. If $L$ is recognized by a DFA $M$, we can construct an NFA for $\text{Suffix}(L)$ by making the start state of the NFA have $\epsilon$-transitions to all states of $M$ that are reachable from the original start state.

Therefore, the language in Option B is NOT regular.