[Solved]: Why does $A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$ generate a context free language for regular $L$?

Problem Detail: 

How can I prove that the language that the operator $A$ defines for regular language $L$ is a context free language.

$A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$, where $x^R$ is the reversed form of $x$.

I understand that since $L$ is regular so does $L^R$.also on my way for a CFG I can reach $w_1$ by the CFG of $L$ concatenation with the one of $L^R$ for making $w_2$. so far I have a CFG, but what promises me that $|w_1|=|w_2|$? how can I generate a grammar that will also keep that in addition to the other conditions?

Asked By : Jozef

Answered By : Kaveh

You can show that it is decided by a PDA.

Check if the input string up to $i$th symbol is in $L$ while pushing them to the stack. Then check if the rest of the string is also in $L^R$ while poping one symbol from the stack for each symbol you read. (Note that if $L$ is a regular language so is $L^R$ and memberships in $L$ and $L^R$ can be checked without by DFAs, i.e. no stack is needed for that part.)

You can guess $i$ nondeterministically.

Best Answer from StackOverflow

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