5
$\begingroup$

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.

$\endgroup$
11
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Yes, I was just about to write this too. $\endgroup$ – Tara B Apr 27 '12 at 19:14
  • $\begingroup$ @Jozef: Are you sure you haven't made a mistake in the question? $\endgroup$ – Tara B Apr 27 '12 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 '12 at 20:50
  • $\begingroup$ @LucasCook: Ah, I guess you're right. $\endgroup$ – Tara B Apr 27 '12 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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