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:
- Assume that the language L is regular.
- By Pigeon-hole principle, any sufficiently long string in L should repeat some state in the DFA, and therefore, the walk contains a “cycle”.
- Show that repeating the cycle some number of times (“pumping” the cycle) yields a string that is not in L.
- 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
- | xy | is less than or equal to m.
- | y | > 0,
- wi xy z = i is also in L for all i = 0, 1, 2, 3, φ, φ
To use this lemma, we need to show:
- For any choice of m,
- For some wÎL that we get to choose (and we will choose one of length at least ‘m’).
- For any way of decomposing w into xyz, so long as |xy| is not greater than m and y is not l,
- 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
- We don’t know m, but let us assume that there is one.
- Choose a string w = anbn, where n >m, so that any prefix of length ‘m’ consists only of a’s.
- 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.
- 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
- We don’t know m, but assume there is one.
- 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.
- We do not know the decomposition of w into xyz but since| xy| £ m, it follows that | z | > 1. As usual, | y | > 0.
- 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^{i }z| is a composite number.
Hence L is not regular.