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!

Thanks

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 : http://cs.stackexchange.com/questions/42709

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback