Another Look at the Pumping Lemma
Introduction
 Begin by defining pumping a string
 Next look pumping in context of a given language
 Informally, we say that a language is pumpable to mean that
the language has one or more strings that are pumpable in that language.
What Is Pumping a String
 Basic definition: To pump a string w is to form new
strings by repeating a given substring of w 0 or more times.
 Example: Let w = abcd
 Select any substring of w: bc, for example
 Pumping substring bc 0 or more times gives these strings:
 ad (bc repeated 0 times)
 a bc d (bc repeated 1 time  this is w)
 a bcbc d (bc repeated 2 times)
 a bcbcbc d (bc repeated 3 times)
 ...
 Spaces added for clarity
 Select another substring of w: c, for example
 Pumping substring c 0 or more times gives these strings:
 abd (c repeated 0 times)
 ab c d (c repeated 1 time  this is w)
 ab cc d (c repeated 2 times)
 ab ccc d (c repeated 3 times)
 ...
 We can describe these sets of strings as:
a(bc)^{i}d, i ≥ 0, and
ab(c)^{i}d, i ≥ 0
More generally we say that if
 w = xyz
 then we pump w by forming the set of strings xy^{i}z, i ≥ 0
Pumping and the Empty String (ie ε)?
 Can we let y = ε?
 That is, w = xyz = xεz = xz
 Then pumping does not produce new strings:
 xy^{i}z =
xε^{i}z = xεz = xz = w
 Bottom line: y can't be ε
Pumpable String and Languages
 Pumping strings is most useful in the context of some language L:
 Consider only w ∈ L
 Choose substring y so that the new strings
(ie xy^{i}z) are all in L
 Example: In L = a(bc)*d, string abcd ∈ L can be
pumped with substring bc:
 ad ∈ L
 abcd ∈ L
 abcbcd ∈ L
 abcbcbcd ∈ L
 But, in L = a(bc)*d, string abcd ∈ L can
NOTbe pumped with substring c:
 abd ∉ L
 ab c d ∈
 ab cc d ∉ L
 ab ccc d ∉ L
 We say that w = abcd is pumpable in L since
substring ab allows w to be pumped to produce strings in
L
 Normally, when we say that a string is pumpable, we mean with respect to
a specific language
 Since without looking at a specific language, every nonempty string is
pumpable.
 We also say, informally, that L is pumpable, meaning that L contains
one or more strings that are pumpable in L.
Example Pumpable Strings and Languages
 L0 = Σ*
 String w=01 ∈ L0 is pumpable
 Let x=0, y=1, z=ε, then
xy^{i}z = 01^{i}ε ∈ L0
 L1 = 0*1*
 String w=011 ∈ L1 is pumpable
 Let x=0, y=1, z=1, then
xy^{i}z = 01^{i}1 ∈ L1
 L2 = 0Σ*0 ∪ 1Σ*1:
 String w=010110 ∈ L2 is pumpable
 Let x=0, y=1, z=0110, then xy^{i}z = 01^{i}0110 ∈ L2
More Than One Way to Divide w
 Many times a string can be pumped with different substrings
 L0 = Σ*
 String w=01 ∈ L0 is pumpable
 Let x=0, y=1, z=ε, then xy^{i}z = 01^{i}ε ∈ L0
 Let x=ε, y=0, z=1, then
xy^{i}z = ε0^{i}1 ∈ L0
 Example: L1 = 0*1*
 String w=011 is pumpable in different ways:
 Let x=0, y=1, z=0, then 01^{i}1 ∈ L1
 Let x=01, y=1, z=ε, then 011^{i} ∈ L1
 A substring that does not pump: x=ε, y=01,
z=1, then (01)^{i}1 ∉ L1
 Example: L2 = 0Σ*0 ∪ 1Σ*1:
 String w=010110 ∈ L2 is pumpable
 Let x=0, y=1, z=0110, then 01^{i}0 ∈ L2
 What other ways to divide are there?
 Example: L3 = 0(101)*0 ∪ 1Σ*1:
 String w=01010 ∈ L3 is pumpable
 Let x=0, y=101, z=0, then 0(101)^{i}0 ∈ L3
 What other ways to divide are there?
Pumpable Strings and Regular Languages
 Start with this fact: All infinite regular languages
contain one or more strings that can be pumped
 Questions:
 What is an infinite regular language
 Are there different strings in a language that can be pumped?
 Can all strings in an infinite regular language be pumped?
 Why is it true?
 How do we use this fact
 Is every language containing pumpable strings a regular
language?
 We answer each question in turn
What Is an Infinite Regular Language?
 Language: Set of strings
 Regular Language: Language accepted by a DFA
 Infinite Regular Language: Regular Language with an infinite
number of strings
 Examples: 0*, Σ*, 0Σ*0
More Than One Way to Choose w?
 There are many pumpable strings in an infinite regular language
 In fact, we will see that an infinite regular language has an infinite number
of pumpable strings.
 L0 = Σ*
 String w=01 ∈ L0 is pumpable
 Other pumpable strings?
 L1 = 0*1* is an infinite regular language:
 String w=011 is pumpable
 Other pumpable strings?
 L2 = 0Σ*0 ∪ 1Σ*1:
 String w=010110 is pumpable
 Other pumpable strings?
 Example: L3 = 0(101)*0 ∪ 1Σ*1:
 String w=01010 ∈ L3 is pumpable
 Other pumpable strings?
One Pumpable String ⇒ Infinite Number of Pumpable Strings
 w=xyz pumpable ⇒ xy^{i}z is pumpable for i
> 0
 Examples: L1, L3
NonPumpable Strings
 Q: Do infinite regular language have strings that are NOT
PUMPABLE?
 A: Let's see ...
 Examples:
 L0 = Σ*
 L1 = 0*1*
 L2 = 0Σ*0 ∪ 1Σ*1:
 L3 = 0(101)*0 ∪ 1Σ*1:
 General Principles:
 Above a certain length, all strings are pumpable
 Below a certain length, some strings may be not pumpable
 Is ε pumpable?
 What length determines pumpability?
Pumping Length
 Every Regular Language has a pumping length
 We call the pumping length p
 w ≥ p ⇒ w is pumpable
 For language L = L(M), and M=(Q,Σ,...), and if p ≥ Q
then p is a pumping length of L
 This relationship is tied to why the PL is true

Why the PL Holds
 Let language L = L(M)
 Let machine M have p states
 Let w ∈ L and
w=w_{1}w_{2}w_{3}...w_{n}
with n ≥ p
 Then there is a computation
q_{0}q_{1}q_{2}q_{3}...q_{n} that accepts w
 The length of the computation is greater than the number of states
 Some state in the computation must be repeated
 because of the Pigeonhole Principle
 The repeated computation forms a loop
 Loop can be repeated i times
 Loop can be repeated 0 times
Pumpable Strings and Regular Languages
 Fact: Every infinite regular language has pumpable strings
 Is this a Fact: Every language with pumpable strings is Regular?
The Pumping Lemma
 If language L is Regular then ∃ p > 0 such that
w ∈ L and w
≥ p then w can be divided into xyz such that
 xy^{i}z ∈ L, i ≥ 0
 y > 0 (ie y ≠ ε)
 xy ≤ p
Using the Pumping Lemma
 To prove that L is not regular
 Assume L is regular
 Then L has a pumping length p
 Find a string w for which
 w ≥ p and
 w cannot be pumped
 String w contradicts the PL
 Conclude that our assumption was false and thus L is NOT regular
Examples Using the Pumping Lemma