2
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I would love to try it, but the alphabet is $\{0,1 \}$ $\endgroup$ – Robert777 Apr 23 '13 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.