[Pumping Lemma] About the cases for y in the xy^iz criterion

[s3a]

Homework Statement

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

Prove that L is not regular using the pumping lemma.

Homework Equations

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 (but you may need to copy-paste the links, as opposed to merely clicking play on the previews in this thread, for that to work) - there's no need to watch the video(s)):

4. https://www.physicsforums.com/threads/non-regular-language-pumping-lemma.945301/

The Attempt at a Solution

When I asked my teacher about the cases in pumping lemma proofs (alluded to in "2. Homework Equations "), he seemed to have no idea what I was talking about. My proof and my teacher's proof can both be found below (in separate quote tags).

Here is what I had done.:

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) The y only contains occurrences of a.
II) The y only contains occurrences of b.
III) The y only contains occurrences of c.
IV) The y contains occurrences of a and b.
V) The y contains occurrences of b and c.
VI) The 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 <= 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 <= 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 <= 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 <= 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 <= 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 <= 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.

This is the solution my teacher provided.:

Assume for contradiction that L is regular and apply the Pumping
Lemma. Let m be the integer in the Pumping Lemma. Take $w = a^m b^1 c^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^i z ∈ L$ for i = 0, 1, 2, . . . This implies that $y = a^k$ for
some k ∈ {1, . . . , m}. Taking i = 0 we get that $xz = a^{m−k} b^1 c^m ∈ L$; however, this
contradicts the definition of L, since (m − k) · 1 6 = m. Contradiction.

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

Any input would be GREATLY appreciated!

 

[KataKoniK]

Both proofs are essentially correct, but there are some differences in the approach and presentation.

Your proof is more thorough and covers all possible cases, but it may be a bit confusing to follow for someone who is not familiar with the pumping lemma. You also use a specific string S = a^2 b^2 c^4, which works for your proof but may not be the most general choice. Additionally, you use the notation "a a^2 b^2 c^4 = a^3 b^2 c^4," which is not technically correct - it should be "a a^2 b^2 c^4 = a^3 b^2 c^6," since you are multiplying the exponents.

Your teacher's proof is more concise and uses a more general string w = a^m b^1 c^m, which is a better choice. However, it may be less clear to someone who is not familiar with the pumping lemma, as it does not explicitly mention the three parts of the lemma. It also uses the notation "any string of the form xy^i z ∈ L," which does not accurately reflect the definition of the pumping lemma (it should be "for some i ≥ 0").

In terms of correctness, both proofs are valid and lead to the same conclusion. It may be helpful to combine the strengths of both proofs to create a more thorough and clear proof. For example, you could use the more general choice of w = a^m b^1 c^m from your teacher's proof, but also explicitly mention the three parts of the pumping lemma and cover all six cases like you did in your proof. This would make the proof more complete and easier to follow for someone who is not familiar with the pumping lemma.