World's most popular travel blog for travel bloggers.

# [Answers] Prove/ Disprove: If $L$ is a CFL then $A(L)$ is a CFL too

, ,
Problem Detail:

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!

Thanks

#### Answered By : Hendrik Jan

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)$?