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ⁱ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)ⁱ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)ⁱ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ⁱz = xεⁱ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

w=xyz

xyⁱz

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ⁱ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

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

See other notes