World's most popular travel blog for travel bloggers.

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

, , No Comments
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!


Asked By : Elimination

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

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback