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

ignougroup
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