Microsoft PowerPoint – CS332-Lec07
BU CS 332 – Theory of Computation
Lecture 7:
• Distinguishing sets, non‐
regularity
• Context‐free grammars
Reading:
“Myhill‐Nerode” note
Sipser Ch 1.4 (optional)
Sipser Ch 2.1
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
Context‐Free Grammars
2/16/2021 CS332 ‐ Theory of Computation 16
Some History
An abstract model for two distinct problems
Rules for parsing natural languages
2/16/2021 CS332 ‐ Theory of Computation 17
Some History
An abstract model for two distinct problems
Specification of syntax and compilation for programming
languages
2/16/2021 CS332 ‐ Theory of Computation 18
1977 ACM Turing Award citation
(John Backus)
For profound, influential, and lasting
contributions to the design of practical high‐
level programming systems, notably through
his work on FORTRAN, and for seminal
publication of formal procedures for the
specification of programming languages.
Context‐Free Grammar (Informal)
Example Grammar
Derivation
2/16/2021 CS332 ‐ Theory of Computation 19
Context‐Free Grammar (Informal)
Example Grammar 𝐺
𝐸 → 𝐸 𝑇
𝐸 → 𝑇
𝑇 → 𝑇 𝐹
𝑇 → 𝐹
𝐹 → 𝐸
𝐹 → 𝑎
𝐹 → 𝑏
Derivation
𝐿 𝐺
2/16/2021 CS332 ‐ Theory of Computation 20
Socially Awkward Professor Grammar
2/16/2021 CS332 ‐ Theory of Computation 21
Socially Awkward Professor Grammar
2/16/2021 CS332 ‐ Theory of Computation 22
Context‐Free Grammar (Formal)
A CFG is a 4‐tuple
• is a finite set of variables
• is a finite set of terminal symbols (disjoint from )
• is a finite set of production rules of the form ,
where and ∗
• is the start symbol
Example: where
2/16/2021 CS332 ‐ Theory of Computation 23
CFG Examples
Give context‐free grammars for the following languages
1. The empty language
2. Strings of properly nested parentheses
3. Strings with equal # of ’s and ’s
2/16/2021 CS332 ‐ Theory of Computation 24
Regular vs. Context‐Free Languages
2/16/2021 CS332 ‐ Theory of Computation 25
A language is context free if it is generated by a context‐free
grammar