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.

Improve this question
$\endgroup$
2
  • 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, 2015 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, 2016 at 12:26

1 Answer 1

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

Improve this answer
$\endgroup$

Your Answer

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

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