- #1
s3a
- 818
- 8
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)):
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!