[Solved]: Prove that context free languages are not closed under swapping prefixes and suffixes

Problem Detail: 

Prove that context free languages aren't closed under this operation: $ A(L) = \{ zyx \mid x,y,z \in \{0,1 \}^*, xyz \in L \} $

Obviously, we need to find a context free language $L$ such that $A(L)$ isn't context free. Here are some of my failed attempts:

Take the language $ L = \{\ 0^n1^n \mid n \in N \} $ and then (since the intersection of a context free language with a regular language is context free) we get: $ A(L) \cap 1^*0^*1^*0^* = \{\ 1^{m}0^{n-k}1^{n-m}0^{k} \mid n,k,m \in N, m,k\le n \} $ which might look promising at first, but unfortunately this language is context free...

I also tried my luck with the following languages:
$ L = \{\ 0^n1^m0^m1^n \mid n,m \in N \} $
$ L = \{\ ww^R \mid w \in \{0,1 \}^* \} $

but these languages didn't help me either...

Asked By : Robert777

Answered By : Hendrik Jan

Did you try $\{\ a^nb^nc^md^m \mid m,n \ge 1 \}$?

Or, if you insist on alphabet $\{0,1\}$, consider $\{\ (01)^n(011)^n(0111)^m(01111)^m \mid m,n \ge 1 \}$?

And be shure to intersect with a nice regular language after the operation, but from your question I see that you know how that works.

Best Answer from StackOverflow

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