**Q: Why do we care about the Pumping Lemma`**
A: We use it to prove that a language is NOT regular.
**Q: How do we do that?**
A: We assume that the language IS REGULAR, and then prove a
contradiction.
**Q: Okay, where does the PL come in?**
A: We prove that the PL is violated. This is a contradiction because the PL holds for all
regular languages.
**Q: Okay, so what is the Pumping Lemma?**
A: Here it is:
- If
*A*is a regular language, then- there is a number
*p*(the pumping length), and - if
*s*is any string in*A*of length at least*p*, then -
*s*can be divided into three pieces,*s = xyz*, that satisfy the following conditions: -
*xy*∈^{i}z*A*, for each*i*≥ 0 - |
*y*| > 0 - |
*xy*| ≤*p*

- there is a number
**Q: Okay, what does the first condition mean?**
A: It means that if **Q: What does the second condition mean?**
A: When we pump, we get different strings. [remember that ε pumped is still ε]
**Q: What does the third condition mean?**
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.
**Q: Okay, lets see how to use the PL to prove that some language is not regular?**
A: Not yet- lets look at a RL first: b(cd)*
**Q: So, what about that language?**
A: First find a machine. Now choose p = 3.
Consider s = bcd and split it up and then see how we can pump it.
**Q: Could we choose a different p for this language?**
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.
**Q: What do you mean when you say "the conditions"?**
A: Usually that means the three conditions that have to hold on xyz.
**Q: Are we ready yet to use the PL to prove that some language is not regular?**
A: Yes, and here's the language: A = b**Q: Sounds simple - why isn't it regular?**
A: Intuition: no history, finite memory, DFA can't count
**Q: So how do we prove A is not regular?**
A: Assume that A is a Regular Language. We know a pumping length exists.
Call it - y = b
^{m}, 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 b^{p+m*i}c^{p}) and so the pumped string would not be in the language (but it must be in the language). - y = c
^{m}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. - y = b
^{k}c^{m}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. **Q: Can I really choose any string that I want?**
A: Yes. And it's critical to find a string that CANNOT be divided properly.
**Q: ?**
A:
**Q: ?**
A:
**Q: ?**
A:
**Q: How do I think about using the conditions?**
A: For any p, EVERY string longer than p must have at least one way to
divide it so that the conditions hold.
**Q: ?**
A:
**Q: Anything else I should know?**
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.
**Q: Since a string in a finite language obviously can't be pumped, does the PL still hold for finite languages?**
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.
**Q: How do I prove the Pumping Lemma?**
A: It goes like this: Let A be a regular language and M=(Q, Σ, &delta, q-
*xyz*can be pumped - |
*y*| > 0 - The repetition must occur within the first
*p*states, and so |*xy*| ≤*p*

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.

Sometimes it means those three conditions and the condition(s) that |s| ≥

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.

By the pigeon-hole principle, the first p+1 states computation must have two equal states. Let

Dr. Okie's Home Page,

Last modified on