Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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 6 '13 at 4:05

1 Answer 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).

share|improve this answer
    
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 6 '13 at 4: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 6 '13 at 4: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 6 '13 at 4: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 6 '13 at 4: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 6 '13 at 6:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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