Pumping Lemma FAQ
Pumping Lemma for Regular Languages
- 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:
-
xyiz ∈ A,
for each i ≥ 0
- |y| > 0
- |xy| ≤ p
- Q: Okay, what does the first condition mean?
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!
- 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.
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.
- 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.
Sometimes it means those three conditions and the condition(s) that |s| ≥
p and/or that s can be divided into 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 = bn cn
- 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 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:
- 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).
- 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.
- 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!
- 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.
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.
- 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, 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:
- xyz can be pumped
- | y| > 0
- The repetition must occur within the first p states, and so | xy|
≤ p
Dr. Okie's Home Page,
Last modified on