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