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

Question

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)):

1. https://youtu.be/dikEDuepOtI?t=393
2. https://youtu.be/Ty9tpikilAo?t=474
3. https://youtu.be/g4e2RElzCSQ?t=1282
4. https://www.physicsforums.com/threads/non-regular-language-pumping-lemma.945301/

---

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!

Answer 1

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.