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 1


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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.