1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Why do you assume that $p=2$? $\endgroup$ – Daniel Mroz Oct 24 '18 at 23:10
  • $\begingroup$ @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. $\endgroup$ – Alfred Kaminski Oct 24 '18 at 23:25
  • $\begingroup$ 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. $\endgroup$ – Daniel Mroz Oct 24 '18 at 23:37
  • $\begingroup$ 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. $\endgroup$ – Alfred Kaminski Oct 25 '18 at 23:24
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So, based on comments on source 2's video, it seems that I was wrong to fix the value of P, but I have a book that has an example that also shows use of cases for y, and it agrees with my sources 2 and 3. In an attempt to see why it may not be in disagreement with my teacher's solution, I tried to think about what my teacher did with the y=a^k part, but that only seems to be taking the case where y is composed of some amount, k, of a symbols into consideration and ignoring other cases of y. Could you please elaborate on why the teacher's solution can avoid (explicitly) discussing cases for y? $\endgroup$ – Alfred Kaminski Oct 25 '18 at 23:22
  • $\begingroup$ Example from book that I was referring to: docdroid.net/Ii5Lk7P/example5p20.pdf (Thanks for your answer, by the way.) $\endgroup$ – Alfred Kaminski Oct 25 '18 at 23:22
  • $\begingroup$ 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$? $\endgroup$ – Alfred Kaminski Oct 25 '18 at 23:22
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Oct 26 '18 at 1:51
  • $\begingroup$ I see that y can take up to m symbols, but shouldn't it / y be able to take less a symbols and take more than zero b symbols, for example? (I say "for example" because there are more cases that I am not mentioning.) Another way of putting it is, in the example I posted ( docdroid.net/Ii5Lk7P/example5p20.pdf ), why is the solution's author not satisfied with just saying 0^k for some integer k = 1, ..., n (which is case 1), and then ignoring cases 2 and 3? (It uses the variable n to denote the pumping length.) $\endgroup$ – Alfred Kaminski Oct 26 '18 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.