# CS代考计算机代写 assembly BU CS 332 – Theory of Computation

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