Language of Palindrome-Prefixed Words

Question

Classify the language $L = \{xx^Rw\ \big|\ (|x| \geq 0\ \wedge |w|\gt 0)\ where\ x,w\in\Sigma^*\}$ as one of:

1. Regular but not Context-Free
2. Context-Free but not Regular
3. Decidable but not Context-Free

Most generally, $\Sigma^*$ can be any regular language (say $(a+b)^*$).

My first thought is that it can't be regular because palindromes themselves are not regular but I'm unsure if it is context-free or not. My hunch is to attempt the pumping lemma for CFL's to show that it is not context-free and, if that works, try to show that $L$ is decidable.

However, this approach feels prone to confirmation bias so I'm seeking some intuition by observing one's thought process in approaching such problems.

Answer 1

Somewhat surprisingly, the language is regular. The key idea here is that you aren't given a $x$ and a $w$, but rather you want all words that can be expressed as $xx^Rw$ for some $x, w$. The only constraints are that $|\,x\,|\ge 0$ and $|\,w\,|>0$.

Hint Since you have free choice of $x$, why not choose $x=\epsilon$, the empty string. Then what will $xx^rw$ have to be?