How can I divide s into uvxyz for the Pumping Lemma?

[mathmari]

Hello and a Happy New Year!!!

Given the language $L=\{w \in \{a,b\}^{*}: w=kkk, \text{for some } k \in \{a,b\}^{*}\}$, I have to show that $L$ is not context free using the Pumping Lemma.

Assuming that $L$ is context free, there is a pumping length $p$ by the pumping lemma.
If I take $s=ababab$, how can I divide it into $uvxyz$ ?

 

[Evgeny.Makarov]

Hello and a Happy New Year!!!

Thanks, and same to you!

If I take $s=ababab$, how can I divide it into $uvxyz$ ?

You are guaranteed to be able to divide (and have the rest of the claim true for) only those words that are longer than the pumping length, which can be greater than 6.

Edit. A better answer would be that $L$ is, in fact, not CF, so the pumping lemma is not applicable to it, and so nobody guarantees that $ababab$ can be divided in such a way as to guarantee that result the lemma talks about.

 

[mathmari]

You are guaranteed to be able to divide (and have the rest of the claim true for) only those words that are longer than the pumping length, which can be greater than 6.

So, do I have to take an other word as $s$ ?

 

[Evgeny.Makarov]

You not only have to take a different word, you have to produce a whole family of words. Indeed, the pumping lemma has the form
\[
L\text{ is CF}\implies\exists n\forall w\in L.\,|w|>n\implies\dots
\]
You apply the contrapositive to show that $L$ is not CF. That is, you prove
\[
\forall n\exists w.\,|w|>n\land\dots
\]
So, you have to find a suitable word (whose pumping instances are not in the language) for all possible pumping lengths $n$.

 

[mathmari]

You not only have to take a different word, you have to produce a whole family of words. Indeed, the pumping lemma has the form
\[
L\text{ is CF}\implies\exists n\forall w\in L.\,|w|>n\implies\dots
\]
You apply the contrapositive to show that $L$ is not CF. That is, you prove
\[
\forall n\exists w.\,|w|>n\land\dots
\]
So, you have to find a suitable word (whose pumping instances are not in the language) for all possible pumping lengths $n$.

I'm a little confused now... Could you explain me how to find this family of words?

 

[Evgeny.Makarov]

The idea is the same as in the pumping lemma for regular languages. The only difference is in the manner of pumping: the lemma for CF languages says that $uv^kxy^kz\in L$ instead of $uv^kw\in L$ for reguar languages. You used the lemma to prove that some languages are not regular, didn't you?

You just need to refute every possible claim that there exists a grammar that generates the language in question. The pumping length for CF languages is read off a grammar. So for every (false) claim that such and such grammar allegedly generates the language, you say the following. If that were true, there would be a pumping length, and all words in the language whose length is greater are split into five parts and can be pumped while remaining in the language. One pretender can say that his grammar corresponds to the pumping length of 100, another one says that her grammar has pumping length 1000. Since you need to refute all such claims, you need an argument that works for all possible lengths. So for each alleged pumping length you find a longer word to which the pumping lemma, if the language is indeed CF, should apply. You then show that you can pump the word out of the language.

 

[mathmari]

The idea is the same as in the pumping lemma for regular languages. The only difference is in the manner of pumping: the lemma for CF languages says that $uv^kxy^kz\in L$ instead of $uv^kw\in L$ for reguar languages. You used the lemma to prove that some languages are not regular, didn't you?

You just need to refute every possible claim that there exists a grammar that generates the language in question. The pumping length for CF languages is read off a grammar. So for every (false) claim that such and such grammar allegedly generates the language, you say the following. If that were true, there would be a pumping length, and all words in the language whose length is greater are split into five parts and can be pumped while remaining in the language. One pretender can say that his grammar corresponds to the pumping length of 100, another one says that her grammar has pumping length 1000. Since you need to refute all such claims, you need an argument that works for all possible lengths. So for each alleged pumping length you find a longer word to which the pumping lemma, if the language is indeed CF, should apply. You then show that you can pump the word out of the language.

For example, could I take the word $s=a^pb^pa^pb^pa^pb^p$ ?

What I've thought is the following:

Let $s=(ab)^{3p}$
By the pumping lemma $s$ can be divided into $uvxyz$, $|uvxyz|=|s|$.
So, $|uv^ixy^iz|=|s|+(i-1)|vy|=3p+(i-1)|vy|$.
For $i=\frac{x-3p}{|vy|}+1$ we have $|uv^ixy^iz|=x$, where $x$ is a big number, greater than $3p$. So, we can take a x that is not of the form of $3p$, so the word does not belong to L.

Could we do it like that? Or, do we have to take cases how we divide the word into $uvxyz$?

 

[Evgeny.Makarov]

For example, could I take the word $s=a^pb^pa^pb^pa^pb^p$ ?

What is $p$?

Let $s=(ab)^{3p}$

$(ab)^{3p}\ne a^pb^pa^pb^pa^pb^p$.

So, $|uv^ixy^iz|=|s|+(i-1)|vy|=3p+(i-1)|vy|$.

Do you mean $\mathbf{6}p+(i-1)|vy|$?

For $i=\frac{x-3p}{|vy|}+1$ we have $|uv^ixy^iz|=x$, where $x$ is a big number

I though that $x$ was a substring of $s$, not a number. OK, let $n=|uv^ixy^iz|$; then $i=\dfrac{n-6p}{|vy|}+1$.

So, we can take a x that is not of the form of $3p$, so the word does not belong to L.

Why is it that when you select $n$ not in the form of $6p$ that the word is not in $L$? How do you know that $n-6p$ is not divisible by $|vy|$? What if $|vy|=1$? Besides, the pumping lemma does not allow you to chose $n=|uv^ixy^iz|$ arbitrarily; you can only choose $i$ arbitrarily.

Or, do we have to take cases how we divide the word into $uvxyz$?

Yes. The idea usually is to take a specific word (given the pumping length) and to show that however it is broken into $u,v,x,y,z$, adding extra $v$ and $y$ takes the word out of the language. Sometimes it helps to take the intersection of the original language with a regular one since such intersection is CF if the original language is. For example, instead of proving that the original language is not CF you can try proving that $L'=\{kkk\mid k=a^mb^n,m>0,n>0\}$ is not CF because $L'=L\cap L''$ where $L''$ is a regular language described by $a^+b^+a^+b^+a^+b^+$ (here $c^+=cc^*$ is the regular expression saying that $c$ occurs at least once).

Edit: Changed "adding extra $v$ and $x$" to "adding extra $v$ and $y$".

 

[mathmari]

What is $p$?

$p$ is the pumping length.

I though that $x$ was a substring of $s$, not a number.

Oh right.. I'm sorry!

Yes. The idea usually is to take a specific word (given the pumping length) and to show that however it is broken into $u,v,x,y,z$, adding extra $v$ and $x$ takes the word out of the language.

For example, taking the word $s=a^pb^pa^pb^pa^pb^p$.
One of the cases of how we divide the word into $uvxyz$ is the following:
Let $u$ contains the first $k$ $a$'s, where $k<p$. So, $u=a^k$.
Also let $vxy=a^m$. ( $v=a^{m_1}, x=a^{m_2}, y=a^{m_3}$, $m_1+m_2+m_3=m$ )
So $z$ is the part of the word that left, $z=a^{p-k-m}b^pa^pb^pa^pb^p$.

Then we find the $uv^ixy^iz=a^ka^{im_1}a^{m_2}a^{im_3}a^{p-k-m}b^pa^pb^pa^pb^p=a^{i(m_1+m_3)+m_2+p-m}b^pa^pb^pa^pb^p=a^{i(m_1+m_3)+p-m_3-m_1}b^pa^pb^pa^pb^p=a^{(i-1)(m_1+m_3)+p}b^pa^pb^pa^pb^p$.

$(i-1)(m_1+m_3)+p$ has to be equal to $p$, but for $i>1$ it's greater than $p$.
So the pumping lemma cannot be applied, so the word is not context free.

Is that one of the cases?
Do I have to take all the possible cases, or is using one of them enough?

 

[Evgeny.Makarov]

For example, taking the word $s=a^pb^pa^pb^pa^pb^p$.
One of the cases of how we divide the word into $uvxyz$ is the following:
Let $u$ contains the first $k$ $a$'s, where $k<p$. So, $u=a^k$.
Also let $vxy=a^m$. ( $v=a^{m_1}, x=a^{m_2}, y=a^{m_3}$, $m_1+m_2+m_3=m$ )
So $z$ is the part of the word that left, $z=a^{p-k-m}b^pa^pb^pa^pb^p$.

Then we find the $uv^ixy^iz=a^ka^{im_1}a^{m_2}a^{im_3}a^{p-k-m}b^pa^pb^pa^pb^p=a^{i(m_1+m_3)+m_2+p-m}b^pa^pb^pa^pb^p=a^{i(m_1+m_3)+p-m_3-m_1}b^pa^pb^pa^pb^p=a^{(i-1)(m_1+m_3)+p}b^pa^pb^pa^pb^p$.

$(i-1)(m_1+m_3)+p$ has to be equal to $p$, but for $i>1$ it's greater than $p$.

You could have simply said that if $v$ and $y$ are parts of the first block of $a$'s, then taking them several ($i$) times will make that first block longer than each of the other two blocks of $a$'s.

Next, you say, "$(i-1)(m_1+m_3)+p$ has to be equal to $p$". Presumably, this has to be true in order for the word to sill have the shape $(a^nb^n)^3$ for some $n$. But what if it does not have this shape, does it mean it is not in the language? The definition of $L$ just says that each word is a cube of another word; that other word does not have to have the shape $a^nb^n$. This is why I suggested taking the intersection of $L$ with $(a^+b^+)^3$: such intersection contains precisely $(a^nb^n)^3$ for various $n$. But even without that it is easy to understand that $a^nb^pa^pb^pa^pb^p$ is not a cube of any word when $n>p$.

so the word is not context free

Each language consisting of just one word is context-free.

Is that one of the cases?

Yes, and an obvious one.

Do I have to take all the possible cases, or is using one of them enough?

I think you know the answer to that. There are two main cases: either one of $u$, $v$ contains the boundary between $a$'s and $b$'s, or they are contained within the blocks. In the first case, pumping $u$ and $v$ will multiply that boundary. In the second case, just two blocks out of three will grow. However, keep in mind what I said about proving that a word is outside $L$: one has to show that it is not a cube of any word and not just of $a^nb^n$.

Edit: The claim in the sentence "This is why I suggested taking the intersection of $L$ with $(a^+b^+)^3$: such intersection contains precisely $(a^nb^n)^3$ for various $n$" is incorrect: the lengths of $a$-blocks and $b$-blocks do not have to coincide. In other words, the intersection is $\{kkk\mid k=a^mb^n,m>0,n>0\}$, just as I said at the end of post #8.

 

[mathmari]

What is $p$?
Sometimes it helps to take the intersection of the original language with a regular one since such intersection is CF if the original language is. For example, instead of proving that the original language is not CF you can try proving that $L'=\{kkk\mid k=a^mb^n,m>0,n>0\}$ is not CF because $L'=L\cap L''$ where $L''$ is a regular language described by $a^+b^+a^+b^+a^+b^+$ (here $c^+=cc^*$ is the regular expression saying that $c$ occurs at least once).

I'll try to prove that $L'$ is not CF.

Considering that $L'$ is CF, so by the pumping lemma, there is a pumping length $p$.

When we had the language $\{kkk\mid k=a^mb^m,m>0\}$, we would take the word $s=a^pb^pa^pb^pa^pb^p$, right? But now $a$ appears $m$ times and $b$ $n$ times, where $m$ and $n$ are not known if they are equal. What word do I have to take now?

 

[Evgeny.Makarov]

When we had the language $\{kkk\mid k=a^mb^m,m>0\}$, we would take the word $s=a^pb^pa^pb^pa^pb^p$, right? But now $a$ appears $m$ times and $b$ $n$ times, where $m$ and $n$ are not known if they are equal. What word do I have to take now?

You can still take $a^pb^pa^pb^pa^pb^p$, which belongs to $L'$, and prove that not all (or maybe none at all) results $uv^ixy^iz$ of pumping belong to $L'$. You just need to show not only that $uv^ixy^iz$ does not have the form $(a^nb^n)^3$ (showing this was never necessary in this problem), but that it does not have the form $(a^nb^m)^3$. The second form is more general, so proving that a word does not have that form is a little harder than showing that it does not have a more restricted form $(a^nb^n)^3$.

But as I said earlier, whether the number of $a$'s and $b$'s is the same does not matter. The important thing is that inserting more $v$'s and $y$'s changes either the number of blocks of $a$'s and $b$'s (each word in $L'$ has 6 such blocks), or it makes the three blocks of $a$'s (or the three blocks of $b$'s) have different number of symbols (each word in $L'$ has equal number of $a$'s in each of the three blocks, and similarly for $b$'s).

 

[mathmari]

So, can I justify that the language is not context free, as you said:

The important thing is that inserting more $v$'s and $y$'s changes either the number of blocks of $a$'s and $b$'s (each word in $L'$ has 6 such blocks), or it makes the three blocks of $a$'s (or the three blocks of $b$'s) have different number of symbols (each word in $L'$ has equal number of $a$'s in each of the three blocks, and similarly for $b$'s).

Or, do I have to explain it further by taking cases?

 

[Evgeny.Makarov]

If you are concerned with being understood, then you need to describe the intended audience. If you need to convince someone that you understand, then you need to indeed understand. Only you can say if you are convinced by the proof and if you can convince others. Besides, what you write depends on the requirements of that someone, and we don't know them.

My advice is first of all to convince yourself to the point that you are able to explain this to a fellow student. Then write as if you are explaining to yourself as you were a couple of days ago, when you still did not know this, or as if you will read this a year from now, when you are likely yo forget many details. Providing more details is usually better than not providing enough.

 

[mathmari]

If you are concerned with being understood, then you need to describe the intended audience. If you need to convince someone that you understand, then you need to indeed understand. Only you can say if you are convinced by the proof and if you can convince others. Besides, what you write depends on the requirements of that someone, and we don't know them.

My advice is first of all to convince yourself to the point that you are able to explain this to a fellow student. Then write as if you are explaining to yourself as you were a couple of days ago, when you still did not know this, or as if you will read this a year from now, when you are likely yo forget many details. Providing more details is usually better than not providing enough.

I tried to explain it more detailed... Could you tell me if the following is right?

One case is that $vy$ contains only $b$'s. Then these come from at most two of the three blocks of $b$. So, $uv^0xy^0z=a^pb^{p-m}a^pb^{p-l}a^pb^{p-n}$, where $m,l,n \geq 0$ (at least one of them is greater than $0$ and one equal to $0$). But in order to belong in $L$, the word has to be of the form $www$ so $w=a^pb^{p-m}=a^pb^{p-l}=a^pb^{p-n} \Rightarrow p-m=p-l=p-n \Rightarrow m=l=n.$
So $uv^0xy^0z$ does not belong to the language.
The other case is the same by replacing $b$ with $a$.

 

[Evgeny.Makarov]

I tried to explain it more detailed... Could you tell me if the following is right?

Briefly, the case you considered is correct, but there are other cases you have not covered.

One case is that $vy$ contains only $b$'s. Then these come from at most two of the three blocks of $b$.

A great beginning.

So, $uv^0xy^0z=a^pb^{p-m}a^pb^{p-l}a^pb^{p-n}$, where $m,l,n \geq 0$ (at least one of them is greater than $0$ and one equal to $0$). But in order to belong in $L$, the word has to be of the form $www$ so $w=a^pb^{p-m}=a^pb^{p-l}=a^pb^{p-n} \Rightarrow p-m=p-l=p-n \Rightarrow m=l=n.$

The only thing here that requires a moment of though is that $a^pb^{p-m}a^pb^{p-l}a^pb^{p-n}=www$ implies that $w$ consists of one block of $a$'s possibly followed by one block of $b$'s. Is it possible that $w$ is described by the regular expression $a^+b^+a^+$? No, because the second block of $a$'s in $www$ would be longer than the first one. There are some other possibilities to refute. It is precisely this fact that you have not addressed above. In contrast, the fact that taking some symbols from two of the three blocks of $b$'s, which initially had equal lengths, makes their lengths differ does not require using algebra; it is obvious.

The other case is the same by replacing $b$ with $a$.

What about the case when $vy$ contains both $a$'s and $b$'s? This case is the reason for considering $L'=\{kkk\mid k=a^mb^n,m>0,n>0\}$ rather the original $L=\{kkk\mid k\in\{a,b\}^*\}$, as described below.

Here is how I would handle this problem. The idea to start with $(a^pb^p)^3$ is correct. (By the way, $p$ does not have to equal or exceed the pumping length. The total length, i.e., $6p$, has to be greater than or equal to the pumping length.) It is clear that if this word is split into $uvxyz$, then adding $v$'s and $y$'s will break the word structure, so it won't have the shape $(a^nb^n)^3$ for some $n$ anymore. I explained it in posts #10 and #12:

The important thing is that inserting more $v$'s and $y$'s changes either the number of blocks of $a$'s and $b$'s (each word in $L'$ has 6 such blocks), or it makes the three blocks of $a$'s (or the three blocks of $b$'s) have different number of symbols (each word in $L'$ has equal number of $a$'s in each of the three blocks, and similarly for $b$'s).

(1) If either $v$ or $y$ contains both $a$ and $b$, then pumping in $v$ and $y$ increases the number of transitions from $a$ to $b$ while in the original word there are precisely three such transitions. (2) If, on the other hand, $v$ consists of only $a$'s or only $b$'s, and similarly for $y$, then adding $v$ and $y$ will not change the number of transitions from $a$ to $b$; however, either the three blocks of $a$'s will not all have the same length, or the three blocks of $b$'s will not all have the same length. (1) and (2) are the only possible cases. I think that this reasoning is sufficiently simple and using algebra would only make it harder to read. Note also that this argument shows that the word with added $v$ and $y$ will not have the shape $(a^nb^n)^3$, but it also shows that it won't even have the shape $(a^mb^n)^3$ where $m$ and $n$ don't have to coincide.

What have we gained so far? If $(a^pb^p)^3=uvxyz$, then $uv^2xy^2z$ does not have the shape $(a^mb^n)^3$. However, this is not sufficient to conclude that $uv^2xy^2z\notin L$, i.e., that $uv^2xy^2z$ does not have the shape $www$ for some $w\in\{a,b\}^*$. Indeed, $w$ can have $a$'s and $b$'s in an arbitrary order, so $www$ does not have to have three blocks of $a$'s and three blocks of $b$'s. Therefore, reasoning in case (1) above is not sufficient. At least, the fact that that $uv^2xy^2z$ does not have the shape $www$ is not obvious. Therefore we'd like to reduce the problem to the situation in the previous paragraph, and for this we consider the intersection of $L$ with the regular language $L''$ described by $(a^+b^+)^3$. If we show that this intersection is $\{kkk\mid k=a^mb^n,m>0,n>0\}$, then we are indeed in that situation and we are done. Suppose that $www\in L\cap L''$. There are four possible cases: (a) $w=a^m$ (b) $w=a^mb^n$, (c) $w=a^mb^naw'$ where $aw'$ ends in $a$, and (d) $w=a^mb^naw'$ where $w'$ ends in $b$. Case (a) is impossible because $www$ constains no $b$'s contrary to the definition of $L''$. Case (c) is also impossible because $www$ ends with an $a$. In case (d), $www$ has more than three transitions from $a$ to $b$. Therefore, the remaining case is (b).

In this proof, the key is identifying all relevant possibilities. Once the cases (1) and (2) as well as (a)--(d) are clearly stated, it is easy to prove them and to see that they are exhaustive. It is possible that this reasoning can be simplified.

Edit. Changes cases (c) and (d) from

"(c) $w=a^mb^naw'$ for some $w'$ ending in $a$, and (d) $w=a^mb^naw'$ for some $w'$ ending in $b$"

to

"(c) $w=a^mb^naw'$ where $aw'$ ends in $a$, and (d) $w=a^mb^naw'$ where $w'$ ends in $b$"

This is because the cases are exhaustive only if $w'$ in case (c) can be empty.

 

[mathmari]

Briefly, the case you considered is correct, but there are other cases you have not covered.

A great beginning.

The only thing here that requires a moment of though is that $a^pb^{p-m}a^pb^{p-l}a^pb^{p-n}=www$ implies that $w$ consists of one block of $a$'s possibly followed by one block of $b$'s. Is it possible that $w$ is described by the regular expression $a^+b^+a^+$? No, because the second block of $a$'s in $www$ would be longer than the first one. There are some other possibilities to refute. It is precisely this fact that you have not addressed above. In contrast, the fact that taking some symbols from two of the three blocks of $b$'s, which initially had equal lengths, makes their lengths differ does not require using algebra; it is obvious.

What about the case when $vy$ contains both $a$'s and $b$'s? This case is the reason for considering $L'=\{kkk\mid k=a^mb^n,m>0,n>0\}$ rather the original $L=\{kkk\mid k\in\{a,b\}^*\}$, as described below.

Here is how I would handle this problem. The idea to start with $(a^pb^p)^3$ is correct. (By the way, $p$ does not have to equal or exceed the pumping length. The total length, i.e., $6p$, has to be greater than or equal to the pumping length.) It is clear that if this word is split into $uvxyz$, then adding $v$'s and $y$'s will break the word structure, so it won't have the shape $(a^nb^n)^3$ for some $n$ anymore. I explained it in posts #10 and #12:
(1) If either $v$ or $y$ contains both $a$ and $b$, then pumping in $v$ and $y$ increases the number of transitions from $a$ to $b$ while in the original word there are precisely three such transitions. (2) If, on the other hand, $v$ consists of only $a$'s or only $b$'s, and similarly for $y$, then adding $v$ and $y$ will not change the number of transitions from $a$ to $b$; however, either the three blocks of $a$'s will not all have the same length, or the three blocks of $b$'s will not all have the same length. (1) and (2) are the only possible cases. I think that this reasoning is sufficiently simple and using algebra would only make it harder to read. Note also that this argument shows that the word with added $v$ and $y$ will not have the shape $(a^nb^n)^3$, but it also shows that it won't even have the shape $(a^mb^n)^3$ where $m$ and $n$ don't have to coincide.

What have we gained so far? If $(a^pb^p)^3=uvxyz$, then $uv^2xy^2z$ does not have the shape $(a^mb^n)^3$. However, this is not sufficient to conclude that $uv^2xy^2z\notin L$, i.e., that $uv^2xy^2z$ does not have the shape $www$ for some $w\in\{a,b\}^*$. Indeed, $w$ can have $a$'s and $b$'s in an arbitrary order, so $www$ does not have to have three blocks of $a$'s and three blocks of $b$'s. Therefore, reasoning in case (1) above is not sufficient. At least, the fact that that $uv^2xy^2z$ does not have the shape $www$ is not obvious. Therefore we'd like to reduce the problem to the situation in the previous paragraph, and for this we consider the intersection of $L$ with the regular language $L''$ described by $(a^+b^+)^3$. If we show that this intersection is $\{kkk\mid k=a^mb^n,m>0,n>0\}$, then we are indeed in that situation and we are done. Suppose that $www\in L\cap L''$. There are four possible cases: (a) $w=a^m$ (b) $w=a^mb^n$, (c) $w=a^mb^naw'$ where $aw'$ ends in $a$, and (d) $w=a^mb^naw'$ where $w'$ ends in $b$. Case (a) is impossible because $www$ constains no $b$'s contrary to the definition of $L''$. Case (c) is also impossible because $www$ ends with an $a$. In case (d), $www$ has more than three transitions from $a$ to $b$. Therefore, the remaining case is (b).

In this proof, the key is identifying all relevant possibilities. Once the cases (1) and (2) as well as (a)--(d) are clearly stated, it is easy to prove them and to see that they are exhaustive. It is possible that this reasoning can be simplified.

Edit. Changes cases (c) and (d) from

"(c) $w=a^mb^naw'$ for some $w'$ ending in $a$, and (d) $w=a^mb^naw'$ for some $w'$ ending in $b$"

to

"(c) $w=a^mb^naw'$ where $aw'$ ends in $a$, and (d) $w=a^mb^naw'$ where $w'$ ends in $b$"

This is because the cases are exhaustive only if $w'$ in case (c) can be empty.

Thank you very much for your help!!!