[Solved]: Pumping lemma for {w | w = ddd}

Problem Detail: 

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?

Asked By : Mary Star

Answered By : tasegula

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19159

3.2K people like this

 Download Related Notes/Documents