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)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 =
xε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 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
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:
- 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 ⇒ 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| ≥ 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=w1w2w3...wn
with n ≥ p
- 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?
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
- xyiz ∈ 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