Pumping Lemma FAQ





Pumping Lemma for Regular Languages

  1. Q: Why do we care about the Pumping Lemma`
  2. A: We use it to prove that a language is NOT regular.
  3. Q: How do we do that?
  4. A: We assume that the language IS REGULAR, and then prove a contradiction.
  5. Q: Okay, where does the PL come in?
  6. A: We prove that the PL is violated. This is a contradiction because the PL holds for all regular languages.
  7. Q: Okay, so what is the Pumping Lemma?
  8. A: Here it is:
  9. Q: Okay, what does the first condition mean?
  10. A: It means that if s is in A then a bunch of other strings (an infinite number of them) are also in the language!
  11. Q: What does the second condition mean?
  12. A: When we pump, we get different strings. [remember that ε pumped is still ε]
  13. Q: What does the third condition mean?
  14. A: The initial xy must be short enough. We want the conditions as strong as possible to make them easy to violate to get a contradiction.
  15. Q: Okay, lets see how to use the PL to prove that some language is not regular?
  16. A: Not yet- lets look at a RL first: b(cd)*
  17. Q: So, what about that language?
  18. A: First find a machine. Now choose p = 3. Consider s = bcd and split it up and then see how we can pump it.
    Now consider s = bcdcd and split it up and then pump it.
    Note that some ways of splitting bcdcd violate condition 3.
    Note that the conditions MUST HOLD for every s that is 3 or longer.
    There may be different ways to split the string. That's okay, because the PL only says that there is a way.
  19. Q: Could we choose a different p for this language?
  20. A: Yes! Once we have found one value for p for which the conditions hold, then the conditions will also hold for every larger value.
  21. Q: What do you mean when you say "the conditions"?
  22. A: Usually that means the three conditions that have to hold on xyz.
    Sometimes it means those three conditions and the condition(s) that |s| ≥ p and/or that s can be divided into xyz.
  23. Q: Are we ready yet to use the PL to prove that some language is not regular?
  24. A: Yes, and here's the language: A = bn cn
  25. Q: Sounds simple - why isn't it regular?
  26. A: Intuition: no history, finite memory, DFA can't count
  27. Q: So how do we prove A is not regular?
  28. A: Assume that A is a Regular Language. We know a pumping length exists. Call it p. Choose s = bpcp. Obviously |s| ≥ p, and so the PL conditions must hold for s. Since the PL conditions hold, we must be able to divide s into xyz. (But we will see that every possible way of dividing s leads to a contradiction.) Now, where could y be? There are only three possibilities:
    1. y = bm, for m > 0 (ie y in the b's). This can't be because when we pump we get too many b's (ie the pumped strings will be bp+m*icp) and so the pumped string would not be in the language (but it must be in the language).
    2. y = cm for m > 0 (ie y in the c's). This can't be for a reason similar to the case above. Also, if y is in the c's, then condition 3 (ie |xy| ≤ p) is violated.
    3. y = bkcm for k,m > 0 (ie y has a mix of b's and c's). This can't be because pumping would cause b's to follow c's and so the pumped string would not be in the language. Also, if y is in the b's and c's, then condition 3 (ie |xy| ≤ p) is violated.
    Thus, we get a contradiction in each of the only possibilities and so the pumping conditions do not hold for the string s. But the PL says that the pumping conditions MUST hold for s. Thus we have a contradiction and so we conclude that A is not regular!
  29. Q: Can I really choose any string that I want?
  30. A: Yes. And it's critical to find a string that CANNOT be divided properly.
  31. Q: ?
  32. A:
  33. Q: ?
  34. A:
  35. Q: ?
  36. A:
  37. Q: How do I think about using the conditions?
  38. A: For any p, EVERY string longer than p must have at least one way to divide it so that the conditions hold.
    Thus, when you are finding a contradiction, you need to find ONE string (there may be more, but you don't care about that) for which there is NO way to divide it up so that the conditions hold.
  39. Q: ?
  40. A:
  41. Q: Anything else I should know?
  42. A: One thing to remember is that every finite language is regular (why?) and so it only makes sense to try to prove violations of the PL for infinite languages.
  43. Q: Since a string in a finite language obviously can't be pumped, does the PL still hold for finite languages?
  44. A: Yes. In this case, the pumping length is larger than the length of the longest string in the language. Thus, there are no strings that are greater than the pumping length, and so there are no strings for which the 3 pumping conditions must hold.
  45. Q: How do I prove the Pumping Lemma?
  46. A: It goes like this: Let A be a regular language and M=(Q, Σ, &delta, q0, F) be a DFA with L(M) = A. Choose p = |Q|. Let s be any string with |s| ≥ p and let the accepting computation for s be r0,r1,...rp, rp+1,...rp+k for some k ≥ 0.

    By the pigeon-hole principle, the first p+1 states computation must have two equal states. Let s = xyz where x is the part of the string accepted appearing before the equal states, y is the part of the string appearing between the equal states, and z is the part of the string appearing after the equal states. Now the following should be clear:
    1. xyz can be pumped
    2. | y| > 0
    3. The repetition must occur within the first p states, and so | xy| ≤ p








Dr. Okie's Home Page,
Last modified on