Microsoft PowerPoint – CS332-Lec07-ann
BU CS 332 – Theory of Computation
Lecture 7:
• Distinguishing sets, non‐
regularity
Reading:
“Myhill‐Nerode” note
Sipser Ch 1.4 (optional)
Mark Bun
February 16, 2021
Distinguishing Sets
2/16/2021 CS332 ‐ Theory of Computation 2
Motivating Questions
• How can we tell if we’ve found the smallest DFA
recognizing a language?
Last time: Introduced distinguishing set method
• Are all languages regular? How can we prove that a
language is not regular?
2/16/2021 CS332 ‐ Theory of Computation 3
A General Technique
Definition: Strings and are distinguishable by if there
exists such that exactly one of or is in .
Ex.
Definition: A set of strings is pairwise distinguishable by if
every pair of distinct strings is distinguishable by .
Ex.
Theorem: If is pairwise distinguishable by , then every DFA
recognizing needs at least states
2/16/2021 CS332 ‐ Theory of Computation 4
𝐴 𝑤 ∈ 0, 1 ∗ 𝑤 ends with 01
Another Example
∗
Theorem: If is pairwise distinguishable by , then every
DFA recognizing needs at least states
2/16/2021 CS332 ‐ Theory of Computation 5
Distinguishing Extension
Which of the following is a distinguishing extension for
and for language ∗ ?
a)
b)
c)
d)
2/16/2021 CS332 ‐ Theory of Computation 6
Historical Note
Converse to the distinguishing set method:
If has no distinguishing set of size , then is
recognized by a DFA with states
Myhill‐Nerode Theorem (1958): is recognized by a DFA
with states iff does not have a distinguishing set of
size
2/16/2021 CS332 ‐ Theory of Computation 7
Non‐Regularity
Theorem: If is pairwise distinguishable by , then every
DFA recognizing needs at least states
Corollary: If is an infinite set that is pairwise
distinguishable by , then no DFA recognizes
2/16/2021 CS332 ‐ Theory of Computation 8
The Classic Example
Theorem: 𝑛 𝑛 is not regular
Proof: Construct an infinite pairwise distinguishable set
2/16/2021 CS332 ‐ Theory of Computation 9
Palindromes
Theorem: ∗ is not regular
Proof: Construct an infinite pairwise distinguishable set
2/16/2021 CS332 ‐ Theory of Computation 10
Now you try!
2/16/2021 CS332 ‐ Theory of Computation 11
∗
Use the distinguishing set method to show that the
following languages are not regular
2/16/2021 CS332 ‐ Theory of Computation 12
Reusing a Proof
2/16/2021 CS332 ‐ Theory of Computation 13
Finding a distinguishing set can take some work…
Let’s try to reuse that work!
0𝑛1𝑛 𝑛 0 = 𝐵𝐴𝐿𝐴𝑁𝐶𝐸𝐷 ∩ 𝑤 all 0s in 𝑤 appear before all 1s
How might we show that
= has an equal # of s and s
is not regular?
Using Closure Properties
2/16/2021 CS332 ‐ Theory of Computation 14
∩ =
(not regular)
If is not regular, we can show a related
language is not regular
any of , , or, for one language, , R, *
By contradiction: If is regular, then is regular.
(regular)
But is not regular so neither is !
Example
2/16/2021 CS332 ‐ Theory of Computation 15
Prove is not regular using
• nonregular language
and
• regular language
all s in appear before all s