# Use the pumping lemma to prove that {www} is not context-free

Use the pumping lemma to prove that the following language is not context-free.

$\qquad L = \{ w w w \mid w \in \{a,b\}^*\}$

I am studying for an exam and really trying to understand this question. For some reason the third w is throwing me off.

I first tried using the string $a^p b^p a^p b^p a^p b^p$ but didn't get very far.

The other string I tried to work through it with was $a^p b^p b^p$

Having a hard time figuring out how exactly to split it up.

Any guidance and explanation would be greatly appreciated.

• You may want to check out our reference question. Note that a) your second string is not in the language and b) you don't get to split it up -- you have to say something for all legal splits. – Raphael Dec 15 '15 at 8:27
• Yes, the third w should throw you off, because that is what makes it not context free. – gnasher729 Aug 30 '16 at 12:26

You could take $w = a^m b a^m$, then you have that $uvxyz = a^m b a^m a^m b a^m a^m b a^m$ $vy = a^l$ with $1\le l\le m$ since there can't be more than one $b$, so you can't pump the $b$. Since $vy$ can only contain $a^m$ without any $b$'s, it will obstruct the balance between the other $a^m$'s.