3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Raphael Dec 15 '15 at 8:27
  • $\begingroup$ Yes, the third w should throw you off, because that is what makes it not context free. $\endgroup$ – gnasher729 Aug 30 '16 at 12:26
2
$\begingroup$

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.
We've found a contradiction while applying the pumping lemma so the language is not Context-Free.

$\endgroup$

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.