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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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