Yet Another Look at the Pumping Lemma
Introduction
 Begin by defining pumping a string
 Next look at pumping and regular languages
 Next look at why pumping works
 Then look at using the pumping lemma
Pumping a String
 To pump string w, take a nonempty substring and
form new strings by repeating the substring 0,1,2,3,... times
 If the substring is y, and w=xyz, then form
xy^{i}z
Examples: Pumping a String
 Example: Let w = abcd
 Select a substring of w: y = 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)
 ...
 a(bc)^{i}d, i ≥ 0
 Select another substring of w: y = 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)
 ...
 ab(c)^{i}d, i ≥ 0
Pumping and the Empty String (ie ε)?
 Why must y be nonempty (ie y ≠ ε?
 If y=ε, then w = xyz = xεz = xz
 Pumping would produce only one string, w:
 xy^{i}z =
xε^{i}z = xεz = xz = w
Pumping and Regular Languages
 For every Regular Language L,
 if w is in L and w is "long enough",
 then w has at least one substring that can be pumped
 and the resulting strings are in L
kli> In other words, w=xyz and xy^{i}z ∈ L
 and y will be "early" in the string
 Define "long enough" and "early" later
 Note: All "long enough" strings are pumpable; some shorter strings may
also be pumpable
Pumping Example
 L1 = a(b ∪ c)*d
 Choose w = abbccd ∈ L1
 Choose x=a, y=b, z=bccd
 xy^{i}z = {abccd, abbccd, abbbccd, abbbbccd, ...}
 Other choices for y: second b, bb, c, cc, bc
 Other choices for w: any string except ?
 L2 = a(b* ∪ c*)d
 Choose w = acccd ∈ L2
 Choices for y: c, cc, ccc (any others?)
 What w does not work?
"Pumpable Languages"
 Informally, we say that a language is pumpable to mean that
 the language has one or more strings that are pumpable in that language.
"Long Enough" and "Early"  the Pumping Length
 Every regular language has a value p
called the pumping length
 Even if we don't know p's value, we know it exists
 "long enough" = w ≥ p
 "early" = xy ≤ p
Why the PL Holds
 Assume machine M accepts language L and M has p states
 If string w ∈ L is longer than p
 then the computation for w has more than p+1 states
 and this computation must repeat a state
 because of the Pigeonhole Principle
 repetition must come within first p symbols
 If a state is repeated in a computation, then it defines a loop
 This loop can be repeated any number of times (including 0)
 Example: Create machine M that accepts a(bc)*d and has 5 states
 The computation for String w = abcbcbcd
can be pumped with substring bc
 String w=abcbcd has computation: 1 2 3 2 3 2 4
 States 2, 3, 2 define a loop (that accepts substring bc )
that can be repeated
The Pumping Lemma
 If language L is Regular
 then ∃ p > 0 such that

if 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 (no matter how it's divided)
 The existance of unpumpable string w longer than p contradicts the PL
 Thus the assumption was false and thus L is NOT regular
Examples Using the Pumping Lemma