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