5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ To be more spesific, I thought of context free languages in a form similar to $L=\{0^n1^n0^m1^m|n,m >=0 \}$, which is CFL, but than A(L) is CFL as well, so it doesn't help me.. it seems to me that every CFL L that I would write down, its A(L) would be CFL as well, apperantly it doesn't correct. $\endgroup$ – Jozef May 3 '12 at 14:14
  • 3
    $\begingroup$ Jozef: Think of some well-known noncontextfree language $L$, and then try to find $L'$ such that $A(L')=L$. $\endgroup$ – sdcvvc May 3 '12 at 15:07
10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ If I got you and the hint right, I am supposed to get that L is of some form of $\{a^mb^mc^ma^mb^mc^m \mid m \ge 0\}$, still it doesn't a CFL. $\endgroup$ – Jozef May 3 '12 at 16:51
  • 2
    $\begingroup$ @Jozef: No, you just need to find $L$ such that the words in $L$ of the form $ww$ are $a^m b^m c^m a^m b^m c^m$ $(m\geq 0)$. $\endgroup$ – Tara B May 3 '12 at 16:55
  • 1
    $\begingroup$ @Jozef: You don't need to be ashamed about not understanding. It took me a little while to think of the example, and I have a PhD partially in language theory. You can see also from your lecturer not knowing straight away that this is not a trivial question. Anyway, I'm going to read about how to do the spoiler now and add it. $\endgroup$ – Tara B May 5 '12 at 12:06

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.