Consider the operation $A(L)$:

$$A(L) = \{ w: w\in L \land w_R \notin L \}$$

where $w_R$ is the reverse of $w$.

Prove/ Disprove: if $L$ is a CFL language so does $A(L)$.

I am almost certain there's a counter-example but I couldn't find a proper one. I'd be glad for help!


  • 1
    $\begingroup$ What have you tried? Where did you get stuck? We do not want to just do your exercise for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$
    – D.W.
    May 18 '15 at 15:33

A simple first step.

Consider any language $K \subseteq \{a,b\}^*$, and let $1,2$ be two new symbols. Let $L = 1\cdot \{a,b\}^* \cdot 2 \cup 2 \cdot K \cdot 1$.

What if $1x2\in A(L)$?


Hint: First, try the following. Prove/disprove: if $L$ is regular, then so is $A(L)$.

Another hint: That should help you narrow down your search for a counterexample. Next, try to come up with a language that you know is context-free but not regular. Try tweaking it a little bit so that it has a non-trivial intersection with its reversal. What do you come up with? I was able to very quickly solve this problem using this approach -- the first example language I came up with, and the first modification I tried, worked.


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.