[Solved]: The operator $A(L)= \{w \mid ww \in L\}$

Problem Detail: 

Consider the operator $A(L)= \{w \mid ww \in L\}$. Apparently, the class of context free languages is not closed against $A$. Still, after a lot of thinking, I can't find any CFL for which $A(L)$ wouldn't be CFL.

Does anyone have an idea for such a language?

Asked By : Jozef

Answered By : Tara B

As an amplification of sdcvvc's hint: You can find a context-free language $L$ such that $A(L) = \{a^m b^m c^m \mid m\geq 0\}$, which as you probably know is not context-free.

So we want to find $L$ such that if $ww\in L$, then $w$ has the form $a^m b^m c^m$. We might as well have $L$ be a sublanguage of $a^*b^*c^*a^*b^*c^*$. Now we just need to put enough restrictions on the words in $L$ so that words of the form $ww$ in $L$ will have the form we require, while ensuring $L$ is still context-free.

Partial spoiler:

A word $a^{m_1} b^{m_2} c^{m_3} a^{m_4} b^{m_5} c^{m_6}$ has the form $ww$ if and only if $m_1 = m_4$, $m_2 = m_5$ and $m_3 = m_6$. Now we can add some restrictions on the $m_i$ for words in $L$ to force them to all be equal in words of the form $ww$. (Hint: we can require $m_1 = m_2$, but then we can't require $m_1 = m_3$ or $m_2 = m_3$, because then $L$ wouldn't be context-free anymore. This isn't a problem though, because we can make use of some of the equalities we already have between the $m_i$.)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1652

 Ask a Question

 Download Related Notes/Documents