# 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)
• ...

• 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)id, i ≥ 0, and ab(c)id, i ≥ 0

• More generally we say that if
• w = xyz
• then we pump w by forming the set of strings xyiz, 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:
• xyiz = iz = 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 xyiz) are all in L

• Example: In L = a(bc)*d, string abcdL can be pumped with substring bc:
• abcdL
• abcbcdL
• abcbcbcdL

• But, in L = a(bc)*d, string abcdL 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 xyiz = 01iε ∈ L0

• L1 = 0*1*
• String w=011 ∈ L1 is pumpable
• Let x=0, y=1, z=1, then xyiz = 01i1 ∈ L1

• L2 = 0Σ*0 ∪ 1Σ*1:
• String w=010110 ∈ L2 is pumpable
• Let x=0, y=1, z=0110, then xyiz = 01i0110 ∈ 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 xyiz = 01iε ∈ L0
• Let x=ε, y=0, z=1, then xyiz = ε0i1 ∈ L0

• Example: L1 = 0*1*
• String w=011 is pumpable in different ways:
• Let x=0, y=1, z=0, then 01i1 ∈ L1
• Let x=01, y=1, z=ε, then 011i ∈ L1
• A substring that does not pump: x=ε, y=01, z=1, then (01)i1 ∉ L1

• Example: L2 = 0Σ*0 ∪ 1Σ*1:
• String w=010110 ∈ L2 is pumpable
• Let x=0, y=1, z=0110, then 01i0 ∈ 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)i0 ∈ 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:
1. What is an infinite regular language
2. Are there different strings in a language that can be pumped?
3. Can all strings in an infinite regular language be pumped?
4. Why is it true?
5. How do we use this fact
6. 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 ⇒ xyiz is pumpable for i > 0

• Examples: L1, L3

## Non-Pumpable 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| ≥ pw 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=w1w2w3...wn with np

• Then there is a computation q0q1q2q3...qn 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?
• No. We'll see why later.

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

• String w contradicts the PL

• Conclude that our assumption was false and thus L is NOT regular

## Examples Using the Pumping Lemma

• See other notes