# The Pumping Lemma for Regular Languages

#### Topics

• Purpose of this unit
• Proof of Pumping Lemma
• Example illustrating proof of Pumping Lemma
• The Pumping Lemma (version 1)
• The Pumping Lemma (version 2)
• Application of the Pumping Lemma to prove the set of palindromes is not regular (long commented version)
• Application of the Pumping Lemma to prove the set of palindromes is not regular (short uncommented version)
• Application of the Pumping Lemma to prove the set of squares is not regular (long commented version)
• Application of the Pumping Lemma to prove the set of squares is not regular (short uncommented version)

#### Content

• Purpose

• Our main goal is to prove a fact about all infinite regular languages that will be helpful in proving that specific languages are nonregular.

• In particular, this pumping lemma will be the main method we use to prove specific languages are not regular.

• Proof of Pumping Lemma

Click here for an illustration of the proof applied to a specific language L)

• Two facts about any infinite regular language L

1. There exists an FA M = (, Q, q0, A, ) such that L(M) = L

2. There exists an infinite number of strings x in L such that |x| |Q|.

• Note this is where we are taking advantage of the extra fact that L is infinite.

• Let x be any string in L such that |x| |Q|.

• Consider the |Q| + 1 prefixes of x

 prefix (0) prefix (1) x1 prefix (2) x1x2 prefix (3) x1x2x3 ... ... prefix (|Q|) x1x2 ... x|Q|

• Key observation:
At least two of these strings (prefixes of x) must end up in the same state

• |Q| states

• |Q|+1 strings (prefixes of x)

• Pigeon hole principle

• There must be a "loop" in x.

• Let prefix (i) and prefix (j) be the first two prefixes of x which end up in the same state of M. Note 0 i < j |Q|.

 x1 x2 ... xi x1 x2 ... xi xi+1 ... xj

• Let q be the state of Q that both prefix (i) and prefix (j) end up in.

• Then (q, xi+1 ... xj) = q.

• This is the loop.

• Pumping Lemma Result

Strings of the form x1x2 ... xi (xi+1 ... xj)k xj+1 ... x|x| are in L for any k 0.

• Follows from the fact that x is in L and the existence of a loop.

• The pumping lemma gets its name from the idea that we can pump this substring xi+1 ... xj as many times as we want and we still get a string in L.

• This is how we will prove that infinite languages such as the set of all palindromes is not regular. There will be no substring that can be pumped in this fashion.

• Pumping Lemma proof applied to a specific example language

• Consider the infinite regular language L corresponding to the language of strings with length 1 mod 3.

1. Here is an FA M with 3 states such that L(M) = L.

2. There exists an infinite number of strings x in L such that |x| 3.

• aaaa aaaaaaa ababaaa aaaaaaabbbbbbaaaaaa

• Let x be any string in L such that |x| 3.

• ababaaa, but I could have chosen many others.

• Consider the first 4 prefixes of ababaaa

 prefix (0) prefix (1) a prefix (2) ab prefix (3) aba

• Key observation:
and aba end up in the same state of M.

• The prefix aba causes a "loop"

• (I, aba) = I.

• Pumping Lemma Result

Strings of the form (aba)kbaaa are in L for any k 0.

• Note for this language, any 3 consecutive characters can be pumped.

• Note the pumped portion v may not begin with x1 or end with x|Q| for other languages.

• Statement 1 of Pumping Lemma

• Let L be any infinite regular language.

• There exists a number n with the following property.

• All strings x in L with length at least n, x can be represented as the concatenation of three strings uvw where:

1. |uv| has length at most n
2. |v| has length at least 1
3. strings of the form uvkw are in L for all k 0.

• Two Questions about Statement 1 of Pumping Lemma

• Statement 2 of Pumping Lemma

• Let L be any infinite regular language.

• There exists an FA M with n states such that L(M) = L.

• All strings x in L with length at least n can be decomposed into a prefix x' of length n and a suffix x'' of length |x| - n.

• The prefix x' can be decomposed into the concatenation of three strings u, v, and w with the following properties:

1. |v| > 0.
2. All strings of the form uvkwx'' are in L for all k 0.

• Proof that L = set of all palindromes is not regular (long commented version).

• We first note that L is infinite.

• We now assume that L is regular.

• COMMENT: We will derive a contradiction and thus be able to conclude this assumption to be false.

• We now apply the Pumping Lemma to L.

• COMMENT: We can do so since it satisifies the two preconditions of being infinite and regular.

• Step 1: there exists an FA M with n = |Q| > 0 states such that L(M) = L.

• COMMENT: Note we cannot specify any specific number n but must reason with n as a variable.

• COMMENT: The only fact we can assume about n is that it is a finite integer.

• Step 2: Consider the string x = anban in L.

• COMMENT: Note we are using our knowledge of the language L to claim this string is in L.

• COMMENT: Step 2 of choosing the correct string to work with is often the crucial step of Pumping Lemma proofs of nonregularity.

• COMMENT: This string x will always be a function of n from Step 1.

• Step 3a: We can decompose anban into a prefix an and a suffix ban.

• Step 3b: By the Pumping Lemma, the prefix an can be decomposed into the concatenation of three strings u, v, and w with the following two properties:

1. |v| > 0

2. uvkwban is in L for all k 0.

• COMMENT: Note at this point we do cannot state what exactly u v and w are.

• Question 3: How many different possibilities for u,v,w are there?

• COMMENT: Note also, though, that we do know that by our choice of x (and thus x'), we know that u,v,w consist only of a's.

• COMMENT: Indeed, this is why we chose anban instead of something like an/2ban/2.

• Step 4: Consider the string s = uwban where k = 0.

• COMMENT: Step 4 of choosing the value of k to use is the second crucial step of Pumping Lemma proofs.

• Step 5: Deriving a contradiction

• Step 5a: The string uw must consist of exactly n a's.

• Note s has only one b, so in order for s to be in L, it must be the case that b is in the middle of s.

• We already know that there are n a's following the one b.

• COMMENT: Note in proving Step 5a, we used arguments specific to L and s.

• Step 5b: There string uw has less than n a's

• uvw was a string consisting of exactly n a's.

• COMMENT: Knowledge specific to the string x.

• From the Pumping Lemma, we know that v contains at least one a.

• COMMENT: This is where we utilize the Pumping Lemma.

• Thus the string uw has fewer than n a's.

• COMMENT: In many proofs, we need to consider several cases for how u, v, and w may have been broken up and we need to show EACH of these cases leads to a contradiction.

• COMMENT: In this example, the one analysis applied to all possible choices of u,v,w and thus we need only one argument.

• COMMENT: If we had chosen x = an/2ban/2, we would have had to consider different cases such as

1. v consists only of a's before the b
2. v consists only of a's after the b
3. v consists of a's followed by b
4. v consists of b followed by a's
5. v consists of a's followed by b followed by a's
6. v consists only of b

• COMMENT: Furthermore, the proof would have been incorrect since we could choose v to be just b and in this case no contradiction could be derived.

• Step 6: Thus our initial assumption that L is regular must be false.

• Step 7: Thus we conclude that L, the set of all palindromes, is not regular.

• Proof that L = set of all palindromes is not regular (short uncommented version).

• We first note that L is infinite.

• We now assume that L is regular.

• We now apply the Pumping Lemma to L.

• Step 1: there exists an FA M with n = |Q| > 0 states such that L(M) = L.

• Step 2: Consider the string x = anban in L.

• Step 3a: We can decompose anban into a prefix an and a suffix ban.

• Step 3b: By the Pumping Lemma, the prefix an can be decomposed into the concatenation of three strings u, v, and w with the following two properties:

1. |v| > 0

2. uvkwban is in L for all k 0.

• Step 4: Consider the string s = uwban where k = 0.

• Step 5: Deriving a contradiction

• Step 5a: The string uw must consist of exactly n a's.

• Note s has only one b, so in order for s to be in L, it must be the case that b is in the middle of s.

• We already know that there are n a's following the one b.

• Step 5b: There string uw has less than n a's

• uvw was a string consisting of exactly n a's.

• From the Pumping Lemma, we know that v contains at least one a.

• Thus the string uw has fewer than n a's.

• Step 6: Thus our initial assumption that L is regular must be false.

• Step 7: Thus we conclude that L, the set of all palindromes, is not regular.

• Proof that L = {ai2 | i 0} is not regular (long commented version).

• We first note that L is infinite.

• We now assume that L is regular.

• COMMENT: We will derive a contradiction and thus be able to conclude this assumption to be false.

• We now apply the Pumping Lemma to L.

• COMMENT: We can do so since it satisifies the two preconditions of being infinite and regular.

• Step 1: there exists an FA M with n = |Q| > 0 states such that L(M) = L.

• COMMENT: Note we cannot specify any specific number n but must reason with n as a variable.

• COMMENT: The only fact we can assume about n is that it is a finite integer.

• Step 2: Consider the string x = an2 in L.

• COMMENT: Note we are using our knowledge of the language L to claim this string is in L.

• COMMENT: Step 2 of choosing the correct string to work with is often the crucial step of Pumping Lemma proofs of nonregularity.

• COMMENT: This string x will always be a function of n from Step 1.

• Step 3a: We can decompose an2 into a prefix an and a suffix an2-n.

• Step 3b: By the Pumping Lemma, the prefix an can be decomposed into the concatenation of three strings u, v, and w with the following two properties:

1. |v| > 0

2. uvkwan2 - n is in L for all k 0.

• Step 4: Consider the string s = uv2wan2 - n where k = 2.

• COMMENT: Step 4 of choosing the value of k to use is the second crucial step of Pumping Lemma proofs.

• Step 5: Deriving a contradiction

• Step 5a: The string s = uv2wan2 - n must consist of at least (n+1)2 a's.

• Note s has more characters than x did since we chose k = 2.

• Since s must be in L, it must get to the "next" string in L which means it must have at least (n+1)2 a's.

• COMMENT: Note in proving Step 5a, we used arguments specific to L and s.

• Step 5b: There string s has less than (n+1)2 a's

• String v has at most n a's.

• COMMENT: From the Pumping Lemma.

• String x has exactly n2 characters.

• COMMENT: specific knowledge about the string x.

• Thus the string s has at most n2 + n < (n+1)2 a's.

• COMMENT: specific mathematical knowledge.

• COMMENT: In many proofs, we need to consider several cases for how u, v, and w may have been broken up and we need to show EACH of these cases leads to a contradiction.

• Step 6: Thus our initial assumption that L is regular must be false.

• Step 7: Thus we conclude that L, the set of all palindromes, is not regular.

• Proof that L = {ai2 | i 0} is not regular (short uncommented version).

• We first note that L is infinite.

• We now assume that L is regular.

• We now apply the Pumping Lemma to L.

• Step 1: there exists an FA M with n = |Q| > 0 states such that L(M) = L.

• Step 2: Consider the string x = an2 in L.

• Step 3a: We can decompose an2 into a prefix an and a suffix an2-n.

• Step 3b: By the Pumping Lemma, the prefix an can be decomposed into the concatenation of three strings u, v, and w with the following two properties:

1. |v| > 0

2. uvkwan2 - n is in L for all k 0.

• Step 4: Consider the string s = uv2wan2 - n where k = 2.

• Step 5: Deriving a contradiction

• Step 5a: The string s = uv2wan2 - n must consist of at least (n+1)2 a's.

• Note s has more characters than x did since we chose k = 2.

• Since s must be in L, it must get to the "next" string in L which means it must have at least (n+1)2 a's.

• Step 5b: There string s has less than (n+1)2 a's

• String v has at most n a's.

• String x has exactly n2 characters.

• Thus the string s has at most n2 + n < (n+1)2 a's.