the pumping lemma

• THE PUMPING LEMMA

  I.e., we can always find a non-empty string y, near the beginning of w, that can be repeated (pumped) an arbitrary number of times (k > 1) or removed (k = 0), producing strings that must belong to the language.

  
• FACTS

  • All finite languages are regular languages
  • The Pumping Lemma can be applied to show that certain infinite languages are not regular
  • But it cannot be used to show that a language is regular!
  • The Pumping Lemma is a necessary but not sufficient condition for a language to be regular! (i.e., there are non-regular languages satisfying the Pumping Lemma)
• PROOFS USING THE PUMPING LEMMA

  Proof by contradiction

  • Hypothesis: we assume that the language is regular
  • Then, if it does not meet the Pumping Lemma, we conclude that the language is not regular
• PROOF EXAMPLE 1

  
• PROOF EXAMPLE 2