# Prove that context free languages are not closed under swapping prefixes and suffixes

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...

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 \}$?
• I would love to try it, but the alphabet is $\{0,1 \}$ Apr 23, 2013 at 19:05