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

Problem Detail: 

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.

Asked By : Jozef

Answered By : Wu Yin

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1536

 Ask a Question

 Download Related Notes/Documents