# 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 xyiz

## 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)id, 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)id, 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:
• xyiz = iz = 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 xyiz ∈ 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(bc)*d
• Choose w = abbccd ∈ L1
• Choose x=a, y=b, z=bccd
• xyiz = {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
1. xyiz ∈ L, i ≥ 0
2. |y| > 0 (ie y ≠ ε)
3. |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

• See other notes