-1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ possible duplicate of How to prove that a language is not context-free? $\endgroup$ – David Richerby Dec 20 '13 at 18:14
  • $\begingroup$ 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? $\endgroup$ – Mary Star Dec 26 '13 at 13:58
  • $\begingroup$ I would try $a^nb^na^nb^na^nb^n$. $\endgroup$ – Yuval Filmus Dec 27 '13 at 14:05
  • $\begingroup$ And is this the only possible string I can take,or can I take also an other one? $\endgroup$ – Mary Star Dec 27 '13 at 23:37
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Dec 28 '13 at 5:37
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – David Richerby Dec 28 '13 at 1:20
  • $\begingroup$ I was really confused how to solve such type of exercises,now I understood,thanks to the answer of @tase92 ! $\endgroup$ – Mary Star Dec 29 '13 at 13:34
  • $\begingroup$ @tase92 So,do I have to take all the possible cases or is it enough to take only one of them? $\endgroup$ – Mary Star Dec 31 '13 at 14:21
  • $\begingroup$ @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. $\endgroup$ – tasegula Dec 31 '13 at 16:19

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.