# Pumping lemma for {w | w = ddd}

I want to use the pumping lemma to show that the following language is not context free: $$L = \{w \in \{a,b\}^* \mid \exists d \in \{a,b\}^*, w=ddd \}$$

We suppose that $L$ is context-free. Then from the pumping lemma there is a pumping length $p$. Which word $s$ do I have to use, that belongs to $L$ and such that dividing that in $uvxyz$, we can show that the pumping lemma is not satisfied? Could you give me a hint?

• possible duplicate of How to prove that a language is not context-free? – David Richerby Dec 20 '13 at 18:14
• We suppose that the L is context-free. Then from the Pumping Lemma there is a pumping length $p$. Which word $s$ do I have to use, that belongs in L and dividing that in $uvxyz$, we can show that the puping lemma is not satisfied?Could you give me a hint? – Mary Star Dec 26 '13 at 13:58
• I would try $a^nb^na^nb^na^nb^n$. – Yuval Filmus Dec 27 '13 at 14:05
• And is this the only possible string I can take,or can I take also an other one? – Mary Star Dec 27 '13 at 23:37
• There are infinitely many other choices that would work. This is just the first one that popped into my mind. It's also probably the simplest. – Yuval Filmus Dec 28 '13 at 5:37

Starting from what Yuval Filmus said:

$w = a^n b^n a^n b^n a^n b^n$ (this word is accepted by your language).

Then you'll have to start to "cut" the word into pieces, multiple times. Start with:

$u = a^j \\ z = a^{n-i-j} b^n a^n b^n a^n b^n \\ vxy = a^i \to v^{i_1}x^{i_2}y^{i_3} = a^i \Rightarrow i_1 + i_2 + i_3 = i$

So now the word looks like this:

$w = uvxyz = {a^j} \:\ a^{ki_1} \:\ a^{i_2} \:\ a^{ki_3} \:\ a^{n-i-j} \:\ b^n a^n b^n a^n b^n$

Now start to simplify it:

$w = a^{ki_1} \:\ a^{i_2} \:\ a^{ki_3} \:\ a^{n-(i_1 + i_2 + i_3)} \:\ b^n a^n b^n a^n b^n =\\ \:\:\ = a^{(k-1)i_1i_1} \:\ a^{i_2} \:\ a^{(k-1)i_3i_3} \:\ a^{n-i_1 - i_2 - i_3} \:\ b^n a^n b^n a^n b^n = \\ \:\:\ = a^{(k-1)i_1} \:\ a^{(k-1)i_3} \:\ a^n \:\ b^n a^n b^n a^n b^n = \\ \:\:\ = a^{(k-1)(i_1 + i_3)} \:\ a^n \:\ b^n a^n b^n a^n b^n = \\ \:\:\ = a^{n(k-1)(i_1 + i_3)} \:\ b^n a^n b^n a^n b^n =$

$i_1, i_3 > 0$ as the v and y must not be the empty word;

For $k > 1, n(k-1)(i_1\ i_3) \neq n$

This is only the simplest case. From here you can say that this is true for $vxy = b^i$, then again for $a^i,b^i$ from the second and last $d\ in\ w=ddd$.

After this, you'll have to take cases like $vxy = a^pb^q$, for each $d\ in\ w=ddd$ and $vxy = b^pa^q$ for each $dd\ in\ w=ddd$.

As you can imagine, the cases go on, but be sure to not repeat yourself: ($u = \varepsilon$ is the same as $u = a^j,\ j = 0$), and be careful with cases that are equivalent.

• Our homework policy is that, if a user asks only for hints, that request should be honoured and a full answer shouldn't be posted. – David Richerby Dec 28 '13 at 1:20
• I was really confused how to solve such type of exercises,now I understood,thanks to the answer of @tase92 ! – Mary Star Dec 29 '13 at 13:34
• @tase92 So,do I have to take all the possible cases or is it enough to take only one of them? – Mary Star Dec 31 '13 at 14:21
• @evinda you'll have to take all of them, because if even for one it works, them it means that the lemma doesn't apply. – tasegula Dec 31 '13 at 16:19