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,kle 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…
$ 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
