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?

Improve this question
$\endgroup$
2
  • $\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
    Commented May 3, 2012 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
    Commented May 3, 2012 at 15:07

1 Answer 1

Reset to default
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$.)

Improve this answer
$\endgroup$
3
  • $\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
    Commented May 3, 2012 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
    Commented May 3, 2012 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
    Commented May 5, 2012 at 12:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.