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/3/2020 CS332 – Theory of Computation 2
Regular?
Construct an NFA for the following languages
{0𝑛1𝑛 | 0 < 𝑛 ≤ 2} 0𝑛1𝑛 0<𝑛≤𝑘}
{0𝑛1𝑛 | 𝑛 > 0}
2/3/2020 CS332 – Theory of Computation 3
Proving a language is not regular
Theorem: 𝐴 = {0𝑛1𝑛 | 𝑛 > 0} is not regular Proof: (by contradiction)
Let 𝑀 be a DFA with 𝑘 states recognizing 𝐴 Consider running 𝑀 on input 0𝑘1𝑘
2/3/2020 CS332 – Theory of Computation 4
Regular or not?
𝐶 = { 𝑤 | 𝑤 has equal number of 1s and 0s}
𝐷 = { 𝑤 | 𝑤 has equal number of 10s and 01s}
2/3/2020 CS332 – Theory of Computation 5
The Pumping Lemma
A systematic way to prove that a language is not regular
2/3/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/3/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/3/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 𝑖 ≥ 0.
2/3/2020
CS332 – Theory of Computation
9
𝑖 = 0: 𝑖 = 1:
𝑖 = 2: 𝑖 = 3:
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. |𝑦| > 0
2. |𝑥𝑦| ≤ 𝑝
3. 𝑥𝑦𝑖𝑧𝐿forall𝑖 ≥ 0
Example:
Let𝐿 = {𝑤|all𝑎’sin𝑤appear
before all 𝑏’s} ; 𝑝 = 1
2/3/2020 CS332 – Theory of Computation 10
Using the Pumping Lemma
Theorem: 𝐴 = {0𝑛1𝑛 | 𝑛 > 0} is not regular Proof: (by contradiction)
Assume instead that 𝐴 is regular. Then 𝐴 has a pumping length 𝑝.
What happens if we try to pump 0𝑝1𝑝?
If 𝐴 is regular, 𝑤 can be split into 𝑤 = 𝑥𝑦𝑧, where 1. |𝑦| > 0
2. |𝑥𝑦| ≤ 𝑝
3. 𝑥𝑦𝑖𝑧𝐴forall𝑖 ≥ 0
2/3/2020 CS332 – Theory of Computation 11
General Strategy for proving 𝐿 is not regular Proof by contradiction: assume 𝐿 is regular.
Then there is a pumping length 𝑝.
2/3/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. YOU win by finding 𝑖 ≥ 0, for which 𝑥𝑦𝑖 𝑧 is not in 𝐿.
If regardless of how the ADVERSARY plays this game, you
can always win, then 𝐿 is nonregular
2/3/2020 CS332 – Theory of Computation 13
Example: Palindromes
Claim: 𝐿 = 𝑤𝑤𝑅 𝑤 ∈ 0,1 ∗} is not regular Proof: Assume 𝐿 is regular with pumping length 𝑝
1.Find𝑤∈𝐿with 𝑤 >𝑝
2. Show that 𝑤 cannot be pumped
Intuitively
2/3/2020 CS332 – Theory of Computation 14
Example: Palindromes
Claim: 𝐿 = 𝑤𝑤𝑅 𝑤 ∈ 0,1 ∗} is not regular Proof: Assume 𝐿 is regular with pumping length 𝑝
1.Find𝑤∈𝐿with 𝑤 >𝑝
2. Show that 𝑤 cannot be pumped
Formally If 𝑤 = 𝑥𝑦𝑧 with |𝑥𝑦| ≤ 𝑝, then…
2/3/2020 CS332 – Theory of Computation 15
Now you try!
Claim:𝐿= 0𝑖1𝑗 𝑖>𝑗≥0}isnotregular
Proof: Assume 𝐿 is regular with pumping length 𝑝
1.Find𝑤∈𝐿with 𝑤 >𝑝
2. Show that 𝑤 cannot be pumped
Intuitively
2/3/2020 CS332 – Theory of Computation 16
Now you try!
Claim:𝐿= 0𝑖1𝑗 𝑖>𝑗≥0}isnotregular
Proof: Assume 𝐿 is regular with pumping length 𝑝
1.Find𝑤∈𝐿with 𝑤 >𝑝
2. Show that 𝑤 cannot be pumped
Formally If 𝑤 = 𝑥𝑦𝑧 with |𝑥𝑦| ≤ 𝑝, then…
2/3/2020 CS332 – Theory of Computation 17
Choosing wisely
Claim: 𝐵𝐴𝐿𝐴𝑁𝐶𝐸𝐷 = 𝑤 𝑤 has an equal # of 0s and 1s} is not regular
Proof: Assume 𝐿 is regular with pumping length 𝑝 1.Find𝑤∈𝐿with 𝑤 >𝑝
2. Show that 𝑤 cannot be pumped
Formally If 𝑤 = 𝑥𝑦𝑧 with |𝑥𝑦| ≤ 𝑝, then…
2/3/2020 CS332 – Theory of Computation 18
Reusing a Proof
Pumping a language can be lots of work… Let’s try to reuse that work!
How else might we show that 𝐵𝐴𝐿𝐴𝑁𝐶𝐸𝐷 is regular? 0𝑛1𝑛 𝑛 ≥ 0} = 𝐵𝐴𝐿𝐴𝑁𝐶𝐸𝐷 ∩ 𝑤 all 0s in 𝑤 appear before all 1s}
2/3/2020 CS332 – Theory of Computation 19
Using Closure Properties
If 𝐴 is not regular, we can show a related language 𝐵 is not regular
𝐵∩𝐶= (regular)
𝐴
(Not regular) any of {∘, ∪, ∩} or, for one language, {¬, R, *}
By contradiction: If 𝐵 is regular, then 𝐵 ∩ 𝐶 (= 𝐴) is regular.
But 𝐴 is not regular so neither is 𝐵! 2/3/2020 CS332 – Theory of Computation 20
Example
Prove 𝐵 = {0𝑖1𝑗|𝑖 ≠ 𝑗} is not regular
using nonregular language 𝐴 = 0𝑛1𝑛 𝑛 ≥ 0
and regular language
𝐶 = 𝑤 all 0s in 𝑤 appear before all 1s}
2/3/2020
CS332 – Theory of Computation 21