Some comments on the Pumping Lemma for regular languages:
by N. Guydosh
10/3/03
· Statement of the theorem. The key logical quantifiers and other conditions have been highlighted:
Let L be an infinite regular language.
Then, $some integer m > 0 such that " w Î L and |w| ³ m,
we can decompose w (ie., $ a partition with the properties below) as
w = xyz
with |xy| £ m and |y| ³ 1
such that wi = xyiz, "i ³ 0 (pumped w) is also in L (ie., wi Î L, "i ³ 0).
· This (above) is a necessary property that all regular languages must possess. If a language does not possess this property (violates the pumping lemma), then it is not regular ... this is a proof by contradiction.
· The pumping lemma is used to prove that a language is not regular, rather than to prove it is regular. It would difficult to use it to prove regularity, because it is too broad in what it is claiming ie., it must be shown to hold for "w Î L and " pumping values i ³ 0.
· It is easier to find a specific counterexample ($w Î L) which violates the pumping lemma and thus proves L is not regular.
· We must think in “negative” logic to prove a violation (contradiction) of the pumping lemma. We must do the following:
o For the given m > 0 (given by the “opponent”), find a specific w Î L, such that |w| ³ m.
o For the partition w = xyz (given by the “opponent”) show that without regard to the specific nature of the partitions x, y, and z (except the inequalities), and without regard to the value of m, we can find some specific pumping value i ³ 0 ($i ³ 0 ), such that wi = xyiz Ï L (the desired contradiction). If our counterexample does not lead to this contradiction, nothing is proven. Either the counterexample was not a good choice, or the language is actually regular – no conclusion could be drawn.
o Showing that we get the contradiction without regard to the nature of the partitions is sometimes troublesome. The only thing you know about the partitions is the |xy| £ m and 1 £ |y| £ m. In addition, all we know about m is that m ³ 1. In order to prove the contradiction and still satisfy these restrictions (including the inequalities) we must show that the contradiction applies to all partitions (subject to the inequalities) and all
m ³ 1. Since the number of partitions is usually very large, this is usually done by categorizing the possible partitions into “cases”. The choice of the counterexample and the inequalities determines the cases. Generally all the “pumping properties” within a given case are the same for all partitions in that case. Commonly, there is only one case (see the
L = {anbn : n ³ 0} in example 4.7 in the text). We then either show that this case produces a contradiction (QED!) or not (Blah!). If there are more that one case (see the L = {(ab)n ak :n > k, k ³ 0} example 4.10 in the text, and in my “example” notes), then we must get the contradiction FOR ALL (") cases (ie., all partitions).
o If you were asked to show that a particular counterexample, w, for some non-regular language did not work, ie., failed to give the desired contradiction, then you must show that at least one case fails to produce a contradiction. This means that at lease one case (or partition) results in
w Î L for all (") i ³ 0. See my example notes or the text on example 4.8 that illustrates counterexamples that do not work.
Supplementary Examples:
Example 1:
L = { (ab)nw : n ³ 0, w Î {a, b}*, and |w| ³ n}
This is a variation of example 4.10 in the text and in the “example” notes.
Opponent gives m > 0.
We choose counterexample w = (ab)m bm Î L, and note that |w| > m (example is legal).
Opponent gives the partition for w = xyz, |xy| £ m, and |y| = k > 0.
xy and thus y are completely contained within the prefix: (ab)m.
In order to get a contradiction, we must guarantee that wi Ï L for some i ³ 0 for all possible partitions. This problem is now very similar to example 4.10 in the text and expanded in my “example notes”. In order not to place any assumptions on the partitions (except those allowed by the pumping lemma), we must show that
wi Ï L for some i ³ 0 for all “cases” which categorize all the partitions within the constraints of the pumping lemma. As in example 4.10, there are 6 cases:
y may be a, b, (ab)j (ab)ja, (ba)j, (ba)jb, where 0 £ j £ m
Note that the first two cases are included in the others, but they are explicitly given for clarity. If you pump down on y (i = 0), you will get contradictions by either not having enough “ab” pairs, or getting format violations in the “ab prefix” (consecutive a’s or b’s in the prefix field in the pumped string). See example 4.10 in the example notes for details. because we can show that w0 Ï L for all cases (partitions), we have a QED.
Example 2:
L = {an : n is a prime number} is not regular.
Show that L = {an : n is a prime number} is not regular.
The “opponent” gives m > 0.
We choose the counter example test word to be
w = ap, where p is the smallest prime greater than m (example is legal).
Opponent gives the partition for w = xyz, |xy| £ m, and |y| = k > 0.
We pump with the particular value i = p + 1.
This gives:
wi = ap-k aik = ap-k+ik
wp+1 = a(k+1)p
but (k+1)p is not a prime since k+1 > 1 (is a product of two integers both of which are not 1).
Thus wp+1 Ï L a contradiction and thus L is not regular since we made no assumptions on m or the partitions except those given by the pumping lemma.
Comments in the meaning of the pumped up string.
Consider the non-regular language L = {anbn : n ³ 0}
In using the pumping lemma, let us for find a general formula for the pumped string.
Given m > 0 from the “opponent”, we choose the counterexample w = ambm .
The opponent comes back with the partitions w = xyz, |y| = k > 0, and |xy| = r £ m
xy must be all a’s:
|<------m------>|<---m---->|
w = aaaaaaaa…aaaaaaaaaaaaabbbbbbbb…bb
| x | y | z |
|<-k->|
|<----r---->|<--m-r->|
From above, we have:
w = ar-kakam-r bm, note the substring to be pumped is ak .
Thus the string pumped by i ³ 0 is
wi = ar-kaikam-r bm,
combining exponents and simplifying, we have the pumped string:
wi = am+k(i-1) bm
Some sample pumped strings are:
w0 = am-k bm, pumped down (i = 0)
w1 = ambm = w, unpumped string (i = 1)
w2 = am+k bm, pumped up (i = 2)
Interpretation:
w0 is the original string with the substring y removed, ie., w0 is distinct from w and is w with k a’s removed. It will go to the final state with out executing the explicit “y loop”. If any y transversal are still needed to process w0, these are included in the z partition.
w1 is the original unmodified w. By construction we chose w such that |w| ³ m, and must transverse the loop due to the pigeon hole principle. The explicit “y loop” in w is taken only once in w because of the way the opponent partitioned w = xyz. If more transversals are needed to process w = w1, these are included in the z partition.
w2 is the string with y repeated: w2 = xyyz = xy2z. w2 is distinct from w and transverses the explicit “y loop” twice. Again, if more transversals are needed to process w2, these are included in the z partition.
In our example, because there is a pumped string which violates the definition of the language (number of a’s and b’s not equal), L is not regular.