1

Let Σ = {a, b, c}. Use the pumping lemma to prove that A = {aibicj | i,j ≥ 0} is not regular. Please make sure that your proof is clear, logical and complete.

The solution that I wrote was:

Assume that A = {aibici | i,j ≥ 0} is regular. Let p be the pumping length given by the pumping lemma. Choose s to be the string apbpcp. Because s is a member of A and s is no longer than p, the pumping lemma guarantees that s can be split into three pieces, s=xyz, where for any i ≥ 0 the string xyiz is in A.

There are two possibilities:

  1. The string y consists only of a's, b's, or c's. In these cases the string xyyz will not have equal numbers of a's or b's, hence xyyz is not a member of A, a contradiction.
  2. The string y consists of more than one kind of symbol, in this case, xyyz will have the a's, b's, or c's out of order. hence xyyz is not a member of A, another contradiction.

My professor only gave me half credit for this solution and crossed out letter's b and c in case #1. He also wrote that neither of these cases can happen if s=apbpcp and |xy| ≤ p, |y| > 0, both of which are required by the PL. I don't understand why this solution is incorrect can someone please explain?

user2357373
  • 21
  • There's nothing incorrect about your proof. It is perhaps a bit less tight than it could be, but you're doing better than 90% of the pumping lemma questions on this site. – Erick Wong Jun 06 '13 at 04:05

1 Answers1

1

The problem, I feel quite sure, is that you really didn’t use the pumping lemma in its standard form, and it’s impossible to tell from what you wrote whether you actually know and understand that form. The pumping lemma says that $s$ can be split as $s=xyz$ in such a way that

  1. $|xy|\le p$,
  2. $|y|>0$, and
  3. $xy^kz\in A$ for all $k\ge 0$.

Thus, the string $xy$ must be wholly contained within the first $p$ characters of $s$, i.e., within the substring $a^p$. Thus, your second case cannot occur, and in your first case the only possibility is that $x=a^i$ and $y=p^j$, where $i\ge 0$, $j\ge 1$, and $i+j\le p$. In that case for any $k\ge 0$ we have

$$xy^kz=a^ia^{kj}a^{p-(i+j)}b^pc^p=a^{p+(k-1)j}b^pc^p\;,$$

which is in $A$ if and only if $k=1$.

That said, he was considerably harsher than I’d have been. Your argument actually shows that a weak version of the pumping lemma suffices to show that $A$ is not regular. Specifically, we need only the fact that there is a pumping length $p$ such that if $s\in A$ with $|s|\ge p$, then $s$ can be decomposed as $s=xyz$ in such a way that (2) and (3) hold. Since this weaker version is certainly true — it follows immediately from the usual pumping lemma — and since your argument does correctly show that it implies the non-regularity of $A$, I’d have given much more than half credit. I’d probably have hesitated between awarding $8$ or $9$ out of $10$, penalizing you a little for a little lack of detail in your explanation of what goes wrong in your second alternative and perhaps a little more for not clearly showing that you knew the pumping lemma (unless, of course, you showed in another problem that you did remember clause (1) above).

Brian M. Scott
  • 616,228
  • but if xy is wholly contained within the substring b^p it is still less than p, I was just trying to show all the cases. – user2357373 Jun 06 '13 at 04:15
  • 1
    @user2357373: The point is that you were discussing cases that cannot actually arise if you use the full strength of the pumping lemma. That suggests that you may not fully understand the pumping lemma and undoubtedly accounts for the deduction in your score. I think that the deduction is excessive, but I do understand what prompted it. – Brian M. Scott Jun 06 '13 at 04:16
  • Sorry, what do you mean by the full strength of the pumping lemma? And why would y = p^j? I thought the full strength of the pumping lemma would be to show every possible case of the pumping lemma. For case 1, I was trying to show that it would be possible for the string y to consist only of a's, only of b's, or only of c's, which would not be in the language of A. For case 2 why would the string have to be wholly contained within the first p characters? if xy fell between a^p and b^p it would still be less than or equal to p. – user2357373 Jun 06 '13 at 04:43
  • @user2357373: Unfortunately, this discussion is making it clear that you don’t fully understand the pumping lemma; if you did, you’d see what your professor was objecting to. You’re not paying attention to clause (1) up there in the statement of the pumping lemma, which says that you can write $s=xyz$ in such a way that $|xy|\le p$. If you do this, $xy$ is necessarily contained entirely within the $a^p$ part of $s$, and it is absolutely impossible for $y$ to contain anything but $a$’s. – Brian M. Scott Jun 06 '13 at 04:48
  • In the cases that I stated |xy| ≤ p for all cases. What part of clause (1) states that xy is contained entirely within a^p part of s? If xy is contained entirely within the b^p part of s |xy| is still ≤ p. – user2357373 Jun 06 '13 at 06:22
  • @user2357373: $xyz=a^pb^pc^p$, and $|xy|\le p$, so $xy$ is contained in the first $p$ characters of $s$, which are all $a$’s. – Brian M. Scott Jun 06 '13 at 06:23
  • My answer actually is based off a solution from _Introduction to the Theory of Computation__ by Michael Sipser. It comes from exercise 1.29a that asks to prove the language A1={0^n1^n2^n | n≥0} is not regular by use of the pumping lemma. The solution is written: – user2357373 Jun 06 '13 at 06:25
  • (a) Assume that A1 = {0n1n2n| n ≥ 0} is regular. Let p be the pumping length given by the pumping lemma. Choose s to be the string 0p1p2p. Because s is a member of A1 and s is longer than p, the pumping lemma guarantees that s can be split into three pieces, s = xyz, where for any i ≥ 0 the string xyiz is in A1. Consider two possibilities: – user2357373 Jun 06 '13 at 06:26
  • The string y consists only of 0s, only of 1s, or only of 2s. In these cases, the string xyyz will not have equal numbers of 0s, 1s, and 2s. Hence xyyz is not a member of A1, a contradiction.
  • The string y consists of more than one kind of symbol. In this case, xyyz will have the 0s, 1s, or 2s out of order. Hence xyyz is not a member of A1, a contradiction.
    • – user2357373 Jun 06 '13 at 06:26
  • @user2357373: Bad pædagogy on his part: he most definitely ought to have pointed out that the only possibility is that $y$ consists only of $0$’s and that his second cases cannot in fact arise. I suspect that he was trying to show some of the other ways in which pumping can move you out of the language, but I don’t think that it was a good idea: I’m sure that you’re not the only person who’s been misled by it. Note: His proof is not actually wrong, and neither is yours, but both contain irrelevant material, since both cover impossible cases. – Brian M. Scott Jun 06 '13 at 06:32
  • Thank you very much Brian, I finally understand. I'm going to have a talk with my professor and show him Sipser's solution. It definitely did throw me off and it lost me points on a pumping lemma questions for CFLs as well. – user2357373 Jun 06 '13 at 06:46
  • @user2357373: You’re very welcome. For what it’s worth, I do think that you have a case for more than half credit, if he gives partial credit between half and full. – Brian M. Scott Jun 06 '13 at 06:48
  • I have a few more questions on some problems I think I was unfairly graded on, would you mind discussing them with me or should I post new questions? – user2357373 Jun 06 '13 at 06:51
  • @user2357373: It would be much better to make them separate questions; the system discourages long strings of comments. – Brian M. Scott Jun 06 '13 at 06:56