# Pumping Lemma Question: About the cases for y in the xy^iz criterion

Problem statement:

Let $$\Sigma = \{a, b, c\}$$, and consider the task of multiplication encoded in the language $$L = \{a^n b^k c^{nk} : n \geq 0, k \geq 0\}$$.

Prove that L is not regular using the pumping lemma.

Relevant sources:

Sources (from three different people) arguing in favour of cases (where the links that are videos are set to the exact frame that I want you to see - there's no need to watch the video(s)):

My attempted solution:

$$L = \{a^n b^k c^{nk} : n ≥ 0, k ≥ 0\}$$

Let us choose the string generated when $$n = k = P = 2$$. That is, let us choose $$S = a^2 b^2 c^4$$ as a string.

Furthermore, let us assume that $$S$$ is regular.

Then, we try to make that string be of the form $$S = xyz$$, and it should meet the criteria of the pumping lemma, which are that

(i) $$x y^i z ∈ L$$

(ii) $$|y| > 0$$

(iii) $$|xy| ≤ P$$

Then, there are six cases, and they are as follows:

I) $$y$$ only contains occurrences of a.

II) $$y$$ only contains occurrences of b.

III) $$y$$ only contains occurrences of c.

IV) $$y$$ contains occurrences of a and b.

V) $$y$$ contains occurrences of b and c.

VI) $$y$$ contains occurrences of a, b and c.

So, for the string $$S$$ to fulfill the criteria of the pumping lemma, it must be shown that (i), (ii) and (iii) each hold true for at least one of I), II), III), IV), V) and VI). That is, for the string to not fulfill the criteria of the pumping lemma, it must fail at least one of the three parts of the pumping lemma for all six of the above cases.

Case I):

Let $$x = a$$, $$y = a$$ and $$z = b^2 c^4$$. Then, it is indeed the case that $$|y| = 1 > 0$$ and that $$|xy| = 2 \leq 2$$. However, if an integer $$i = 2$$ is chosen, then a string $$a a^2 b^2 c^4 = a^3 b^2 c^4 ∉ L$$ is obtained. So, case I) fails.

Case II):

Let $$x = a^2$$, $$y = b^2$$ and $$z = c^4$$. Then, it is indeed the case that $$|y| = 2 > 0$$, but it is not the case that $$|xy| = 4 \leq 2$$, and so case II) fails. (There is no need to examine part (i) of the pumping lemma.)

Case III):

Let $$x = a^2 b^2$$, $$y = c^2$$ and $$z = c^2$$. Then, it is indeed the case that $$|y| = 2 > 0$$, but it is not the case that $$|xy| = 6 \leq 2$$. So, case III) fails.

Case IV):

Let $$x = a$$, $$y = a b^2$$ and $$z = c^4$$. Then, it is indeed the case that $$|y| = 3 > 0$$, but it is not the case that $$|xy| = 4 \leq 2$$. So, case IV) fails.

Case V:

Let $$x = a^2$$, $$y = b^2 c$$ and $$z = c^3$$. Then, it is indeed the case that $$|y| = 3 > 0$$, but is not the case that $$|xy| = 5 \le 2$$. So, case V) fails.

Case VI:

Let $$x = a$$, $$y = a b^2 c$$ and $$z = c^3$$. Then, it is indeed the case that $$|y| = 4 > 0$$, but it is not the case that $$|xy| = 5 \leq 2$$. So, case VI) fails.

Then, because all six cases have failed at least one of the pumping lemma’s criteria, it follows that the language $$L$$ is not regular.

My teacher's solution:

Assume for contradiction that $$L$$ is regular and apply the Pumping Lemma. Let $$m$$ be the integer in the Pumping Lemma. Take $$w = a^mb^1c^m$$. Since $$w ∈ L$$ and $$|w| ≥ m$$, we can write $$w = xyz$$ such that $$|xy| ≤ m$$ and $$|y| ≥ 1$$ and any string of the form $$xy^iz ∈ L$$ for $$i = 0, 1, 2, \dots$$ This implies that $$y =a^k$$ for some $$k ∈ \{1, \dots , m\}$$. Taking $$i = 0$$, we get that $$xz = a^{m−k}b^1c^m ∈ L$$; however, this contradicts the definition of $$L$$, since $$(m − k) \cdot 1 \neq m$$. Contradiction.

Are we both correct? Is at least one of us wrong? Why?

Any input would be greatly appreciated!

• Why do you assume that $p=2$? Oct 24 '18 at 23:10
• @Daniel Mroz: According to the videos from sources 2 and 3 that I linked to (which are from two different people), one can choose an arbitrary p as long as the pumping lemma's criteria are upheld, and I (arbitrarily) chose P = 2, for simplicity. Oct 24 '18 at 23:25
• But what if $p=3$? or 4? You’ve only shown that the pumping length can’t be 2. It could be some other number, in which case the pumping lemma might hold. Oct 24 '18 at 23:37
• Thanks for your answer; it appears that the main video I was watching was incorrect with regard to this, according to at least one comment in the video's comment section. I'm still unclear about the cases for y, though, as explained in my comment to Yuval Filmus' answer. Oct 25 '18 at 23:24

Your proof doesn't work, since the pumping lemma only applies to large enough words. The pumping lemma states that if a language $$L$$ is regular, then there exists a constant $$m$$ such that all words in $$L$$ of length at least $$m$$ have a certain decomposition $$xyz$$ such that $$|xy| \leq m$$, $$y \neq \epsilon$$, and $$xy^iz \in L$$ for all $$i \geq 0$$. However, there is no guarantee for words of length smaller than $$m$$.
In your case, the word that you chose has size 8, which might conceivably be smaller than $$m$$, and so is not guaranteed to have the decomposition $$xyz$$ satisfying the properties stated above.
As an aside, if $$L$$ is finite than $$m$$ has to be larger than the size of all words in $$L$$ (why?), and in that case the pumping lemma cannot be applied to pump any word.
• P.S. Since you brought it up, about your tangential comment, is it because the pumping length, m, being larger ensures that no pumping can be done since, for any given word, w, it has to be the case that $|w| \geq m$? Oct 25 '18 at 23:22
• Your teacher’s proof looks correct. There are no cases to consider since $y$ is guaranteed to come from the first $m$ symbols, which are all $a$s. Oct 26 '18 at 1:51