Pumping Lemma

Principle of Pumping Lemma

• If an infinite language is regular, it can be defined by a DFA.
• The DFA has some finite number of states (say).
• Since the language is infinite, some strings of the language should have length > n.
• For a string of length > n accepted by the DFA, the walk through the DFA must contain a cycle.
• Repeating the cycle an arbitrary number of times should yield another string accepted by the DFA.

The “pumping lemma” for regular languages is another way of showing that a given infinite language is not regular. The proof is always done by “contradiction”. The technique that is followed is as outlined below:

1. Assume that the language L is regular.
2. By Pigeon-hole principle, any sufficiently long string in L should repeat some state in the DFA, and therefore, the walk contains a “cycle”.
3. Show that repeating the cycle some number of times (“pumping” the cycle) yields a string that is not in L.
4. Conclude that L is not regular.

Applying the Pumping Lemma

Definition of Pumping Lemma

If L is an infinite regular language, then there exists some positive integer ‘m’ such that any string wÎL, whose length is ‘m’ or greater can be decomposed into three parts, xyz where

1. | xy | is less than or equal to m.
2. | y | > 0,
3. wi xy z = i is also in L for all i = 0, 1, 2, 3, φ, φ

To use this lemma, we need to show:

1. For any choice of m,
2. For some wÎL that we get to choose (and we will choose one of length at least ‘m’).
3. For any way of decomposing w into xyz, so long as |xy| is not greater than m and y is not l,
4. We can choose an i such that xyiz is not in L.

Example 1: Prove that L = {a nbn : n ³ 0} is not regular.

Solution

1. We don’t know m, but let us assume that there is one.
2. Choose a string w = anbn, where n >m, so that any prefix of length ‘m’ consists only of a’s.
3. We don’t know the decomposition of w into xyz, but since | xy| £ m, xy must consist entirely of a’s. Moreover, y cannot be empty.
4. Choose i = 0. This has the effect of dropping | y | a’s out of the string, without affectng the number of b’s. The resultant string has fewer a’s than b’s, hence does not belong to L.

Therefore L is not regular.

Example 1.8.3: Show that L = {a n : n is a prime number} is not regular.

Solution

1. We don’t know m, but assume there is one.
2. Chose a string w = an where n is a prime number and | xyz| = n > m 1. (This can always be done because there is no largest prime number). Any prefix of w consists entirely of a’s.
3. We do not know the decomposition of w into xyz but since| xy| £ m, it follows that | z | > 1. As usual, | y | > 0.
4. Since | z| >1, | xy| >1.. Choose i =| xz|. Then | xyi z| = | xz| | y| | xz| = (1 | y| ) | xz|.

Since (1 | y |) and | xz | are each greater than 1, the product must be a composite number. Therefore | xyⁱ z| is a composite number.

Hence L is not regular.