# Closure against the operator $A(L)=\{ww^Rw \mid w \in L \wedge |w| \lt 2007\}$

I would like your help with the following question:

Let $L$ be a language, and operator $A(L)=\{\,ww^Rw \mid w \in L\ \wedge\ |w| \lt 2007\,\}$ where $x^R$ is the reversed string of $x$. Which of the following statements are correct?

1. If $L$ is regular so $A(L)$ is regular.
2. If $L$ is a CFL which is not regular then $A(L)$ is CFL which is not regular.
3. If $L$ is a CFL which is not regular, then $A(L)$ is a CFL which may or may not be regular.
4. If $L$ is not a CFL then $A(L)$ is not CFL.

What does the fact that $|w|< 2007$ help me with the decision? For (2) I can choose $O^n1^n$ and I get that $0^n1^{2n}0^{2n}1^n$, which is not regular, but for (3),(4) I can't find an examples to refute it. The answer is 3, but I can't understand why, since $A(L)= ww^R \circ w$ but $ww^R$ is not regular.

## 1 Answer

Since $|w| < 2007$, the number of strings like $ww^Rw$ is finite. So $A(L)$ is finite for all $L$ and is hence regular.

• Yes, I was just about to write this too. – Tara B Apr 27 '12 at 19:14
• @Jozef: Are you sure you haven't made a mistake in the question? – Tara B Apr 27 '12 at 19:15
• @Tara: looks like a misleading multiple choice exam question to me. (In my experience, questions like this end up testing notation, primarily.) – Lucas Cook Apr 27 '12 at 20:50
• @LucasCook: Ah, I guess you're right. – Tara B Apr 27 '12 at 21:07