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, q₀, 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) x₁
  prefix (2) x₁x₂
  prefix (3) x₁x₂x₃
  ... ...
  prefix (|Q|) x₁x₂ ... 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|.
    
    x₁ x₂ ... x_i
    
    x₁ x₂ ... x_i x_i+1 ... x_j
  - Let q be the state of Q that both prefix (i) and prefix (j) end up in.
  - Then (q, x_i+1 ... x_j) = q.
    - This is the loop.
- Pumping Lemma Result
  Strings of the form x₁x₂ ... x_i (x_i+1 ... x_j)^k x_j+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 x_i+1 ... x_j 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 x₁ 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 uv^kw are in L for all k 0.
- Two Questions about Statement 1 of Pumping Lemma
  - 1) What does the number n correspond to in the proof?
  - 2) What do the strings u, v, and w correspond to in the proof?
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:

|v| > 0.
All strings of the form uv^kwx'' are in L for all k 0.
Proof that L = set of all palindromes is not regular (long commented version).
- 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 = aⁿbaⁿ 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 aⁿbaⁿ into a prefix aⁿ and a suffix baⁿ.
- Step 3b: By the Pumping Lemma, the prefix aⁿ can be decomposed into the concatenation of three strings u, v, and w with the following two properties:
  1. |v| > 0
  2. uv^kwbaⁿ 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 aⁿbaⁿ instead of something like a^n/2ba^n/2.
- Step 4: Consider the string s = uwbaⁿ 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.
  - Steps 5a and 5b lead us to a contradiction.
  - 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 = a^n/2ba^n/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 = aⁿbaⁿ in L.
- Step 3a: We can decompose aⁿbaⁿ into a prefix aⁿ and a suffix baⁿ.
- Step 3b: By the Pumping Lemma, the prefix aⁿ can be decomposed into the concatenation of three strings u, v, and w with the following two properties:
  1. |v| > 0
  2. uv^kwbaⁿ is in L for all k 0.
- Step 4: Consider the string s = uwbaⁿ 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.
  - Steps 5a and 5b lead us 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 = {a^i² | 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 = a^n² 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 a^n² into a prefix aⁿ and a suffix a^n²-n.
- Step 3b: By the Pumping Lemma, the prefix aⁿ can be decomposed into the concatenation of three strings u, v, and w with the following two properties:
  1. |v| > 0
  2. uv^kwa^{n²
    - n} is in L for all k 0.
    - COMMENT: Note at this point we do cannot state what exactly u v and w are.
    - Question 4: How many different possibilities for u,v,w are there?
    - COMMENT: Note also, though, that we do know that by the structure of L and our choice of x (and thus x'), we know that u,v,w consist only of a's.
- Step 4: Consider the string s = uv²wa^{n²
  - 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 = uv²wa^{n²
    - n} must consist of at least (n+1)² 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)² 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)² a's
    - String v has at most n a's.
      - COMMENT: From the Pumping Lemma.
    - String x has exactly n² characters.
      - COMMENT: specific knowledge about the string x.
    - Thus the string s has at most n² + n < (n+1)² a's.
      - COMMENT: specific mathematical knowledge.
  - Steps 5a and 5b lead us to a contradiction.
  - 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 = {a^i² | 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 = a^n² in L.
- Step 3a: We can decompose a^n² into a prefix aⁿ and a suffix a^n²-n.
- Step 3b: By the Pumping Lemma, the prefix aⁿ can be decomposed into the concatenation of three strings u, v, and w with the following two properties:
  1. |v| > 0
  2. uv^kwa^{n²
    - n} is in L for all k 0.
- Step 4: Consider the string s = uv²wa^{n²
  - n} where k = 2.
- Step 5: Deriving a contradiction
  - Step 5a: The string s = uv²wa^{n²
    - n} must consist of at least (n+1)² 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)² a's.
  - Step 5b: There string s has less than (n+1)² a's
    - String v has at most n a's.
    - String x has exactly n² characters.
    - Thus the string s has at most n² + n < (n+1)² a's.
  - Steps 5a and 5b lead us 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.
Answers to all four questions.

Regular Languages Chapter (up one level)
Table of Contents (up two levels)

prefix (0)
prefix (1)	x₁
prefix (2)	x₁x₂
prefix (3)	x₁x₂x₃
...	...
prefix (\|Q\|)	x₁x₂ ... x_\|Q\|

x₁	x₂	...	x_i
x₁	x₂	...	x_i	x_i+1	...	x_j