# How to construct context-free language $L$ to prove $L′=\{x|xx∈L\}$ is not context-free?

Can someone please explain me how to solve this?

In this post here was one user sketching the solution but I still don't understand how to construct a context-free language $$L$$ in such a way that the words in $$L$$ of the form $$ww$$ are $$a^mb^mc^ma^mb^mc^m(m≥0)$$. How does the grammar for L looks like? What equalities have the grammar to ensure and why?

Thanks!

Take a look at $$L = \{a^nb^nc^ma^mb^kc^l : n, m, k, l \geq 0\}.$$

Now take some $$x \in L$$ with $$x = ww$$, then $$x = a^nb^nc^ma^mb^kc^l$$ for some $$n, m, k, l \geq 0$$. There's only one possible way to split $$x$$ into two equal parts $$w$$:

$$w = a^nb^nc^m = a^mb^kc^l.$$

Note that for distinct symbols $$c_i$$, $$c_1^{n_1}c_2^{n_2}...c_k^{n_k} = c_1^{m_1}c_2^{m_2}...c_k^{m_k}$$ implies $$n_i = m_i$$ for all $$i$$. From this we know that

1. $$n = m$$,
2. $$n = k$$, and
3. $$m = l$$.

So from 1. it follows that $$A(L) = \{a^nb^nc^n : n \geq 0\}$$ which is known to be not context-free. To prove that $$L$$ is context free, note that $$L$$ can be generated by the following context-free grammar with start variable $$S$$:

$$S \to ABCD$$ $$A \to aAb | \varepsilon$$ $$B \to cBa | \varepsilon$$ $$C \to bC | \varepsilon$$ $$D \to cD | \varepsilon$$

• That makes so sense, thanks! Feb 13 at 22:38
• @shinichi Glad to hear :) Feb 13 at 22:51
• Did you mean something along the lines of 1.-3. by "What equalities have the grammar to ensure"? I wasn't entirely sure what was meant by that. Feb 13 at 22:51
• yes that's what I meant! One clarification question: Why is it $a^m$ and not e.g. $a^s$ with $s \geq 0$? One thing that comes to my mind is to ensure that the only combination to split $x$ in equal parts $w$ is $w=a^n b^n c^m=a^mb^kc^l$. If $L=\{a^nb^nc^m=a^sb^kc^l| n,m,s,k,l \geq 0\}$ then there would be the possiblity of the word $ww=cc$. Is that the reason? Feb 13 at 23:00
• Yes, exactly! A nice way to get to a solution like mine or the one by Hendrik Jan is by starting off with your example language, setting up equations like 1.-3. for it, and then to figure out what additional restrictions on $m, s, k, l$ you would need to prove $A(L) = \{a^nb^nc^n : n \geq 0\}$. Feb 13 at 23:20

Context-free languages are not closed under intersection. We start there. The relevant example is here that $$\{ a^p b^p c^q \mid p,q\ge 0 \} \cap \{ a^p b^q c^q \mid p,q\ge 0 \} = K$$, where $$K = \{ a^m b^m c^m \mid m\ge 0 \}$$ is not context-free.

The two languages each force a pair of letters to have the same number.

For your question we set $$L = \{ a^p b^p c^q \mid p,q\ge 0 \} \cdot \{ a^p b^q c^q \mid p,q\ge 0 \}$$. Or, written differently $$L = \{ a^p b^p c^q a^r b^s c^s \mid p,q,r,s\ge 0 \}$$. If a string in $$L$$ is of the form $$xx$$ the two $$abc$$-halves must be equal. Thus of the form $$x= a^m b^m c^m$$.

• Thanks thats a neat way to solve it! I didnt consider closure properties. The decision to concatenate with $\{a^pb^qc^q | p,q\geq 0\}$ is to ensure that there is no other word in the form $ww$ in $L$ then $abcabc$, right? Feb 13 at 23:07