BU CS 332 – Theory of Computation
Lecture 4:
• Non‐regular languages
Reading: Sipser Ch 1.4
• Pumping Lemma
Mark Bun February 3, 2020
The Philosophical Question
• We’ve seen techniques for showing that languages are regular
• Could it be the case that every language is regular?
2/4/2020 CS332 ‐ Theory of Computation 2
Regular?
Construct an NFA for the following languages
𝑛𝑛
𝑛𝑛
𝑛𝑛
2/4/2020 CS332 ‐ Theory of Computation 3
Proving a language is not regular
Theorem: 𝑛 𝑛 Proof: (by contradiction)
is not regular
Let be a DFA with Consider running
states recognizing
2/4/2020 CS332 ‐ Theory of Computation
4
on input
𝑘𝑘
Regular or not?
has equal number of
s and
s
has equal number of
s and
s
2/4/2020 CS332 ‐ Theory of Computation
5
The Pumping Lemma
A systematic way to prove that a language is not regular
2/4/2020 CS332 ‐ Theory of Computation 6
Why do we teach this?
Cons:
• The statement is difficult (5 quantifiers!)
• Some non‐regular languages can still be pumped
Pros:
• Proof illuminates essential structure of finite automata
• Generalizes to other models of computation / classes of
languages (CFLs, self‐assembly) • Applying it can be fun!
2/4/2020 CS332 ‐ Theory of Computation 7
Intuition for the Pumping Lemma
Imagine a DFA with states that recognizes strings of length
Idea: If you can go around the cycle once, you can go around 0 or 2,3,4… times
2/4/2020 CS332 ‐ Theory of Computation 8
Pumping Lemma (Informal)
Let be a regular language. Let be a “long enough” string in .
…
0 𝑖 𝑗 || Then we can write such that for
every
2/4/2020 CS332 ‐ Theory of Computation
9
Pumping Lemma (Formal)
Let be a regular language.
Then there exists a “pumping length”
such that
For every where , can be split into three parts
where:
1.
2.
3. 𝑖
all sin appear before all s
2/4/2020
CS332 ‐ Theory of Computation
10
for all
Example: Let
Using the Pumping Lemma
Theorem: 𝑛 𝑛 Proof: (by contradiction)
is not regular is regular. Then
Assume instead that pumping length
has a
.
What happens if we try to pump 𝑝 𝑝?
If is regular, can be split into , where 1. |𝑦| 0
2. |𝑥𝑦| 𝑝
3. 𝑥𝑦𝑖𝑧𝐴forall𝑖 0
2/4/2020 CS332 ‐ Theory of Computation 11
General Strategy for proving
is not regular
Proof by contradiction: assume Then there is a pumping length
is regular.
2/4/2020 CS332 ‐ Theory of Computation
12
.
Pumping Lemma as a game
1. YOU pick the language 𝐿 to be proved nonregular.
2. ADVERSARY picks a possible pumping length 𝑝.
3. YOU pick 𝑤 of length at least 𝑝.
4. ADVERSARY divides 𝑤 into 𝑥, 𝑦, 𝑧, obeying rules of the Pumping Lemma: |𝑦| 0 and |𝑥𝑦| 𝑝.
5. YOUwinbyfinding𝑖0,forwhich𝑥𝑦 𝑧isnotin𝐿.
If regardless of how the ADVERSARY plays this game, you
can always win, then is nonregular
2/4/2020 CS332 ‐ Theory of Computation 13
Example: Palindromes
Claim: ∗ is not regular
Proof: Assume 1. Find
is regular with pumping length with
2. Show that Intuitively
cannot be pumped
2/4/2020
CS332 ‐ Theory of Computation 14
Example: Palindromes
Claim:
∗ is not regular
is regular with pumping length
Proof: Assume 1. Find
with
cannot be pumped
2. Show that Formally
If
= with | | , then…
2/4/2020
CS332 ‐ Theory of Computation
15
Now you try!
Claim: Proof: Assume
is not regular
is regular with pumping length
1. Find
with
cannot be pumped
2. Show that Intuitively
2/4/2020
CS332 ‐ Theory of Computation 16