PowerPoint Presentation
BU CS 332 – Theory of Computation
Lecture 8:
Test 1 Review
Reading:
“Myhill-Nerode” note
Sipser Ch 1.4 (optional)
Sipser Ch 2.1
Mark Bun
February 16, 2021
Mea Culpa
What I wrote:
Let 𝐿 = {𝑤𝑤 | 𝑤 = 𝑤𝑅} and consider the distinguishing
set 𝑆 = 0𝑛 𝑛 ≥ 0}. For 𝑥 = 0𝑛 and 𝑦 = 0𝑚, 𝑚 ≠ 𝑛,
which of the following is a distinguishing extension for 𝑥
and 𝑦?
a) 𝑧 = 0𝑛
b) 𝑧 = 1𝑛
c) 𝑧 = 10𝑛
d) 𝑧 = 01𝑛
2/17/2021 CS332 – Theory of Computation 2
Mea Culpa
What I meant to write:
Let 𝐿 = {𝑤 | 𝑤 = 𝑤𝑅} and consider the distinguishing
set 𝑆 = 0𝑛 𝑛 ≥ 0}. For 𝑥 = 0𝑛 and 𝑦 = 0𝑚, 𝑚 ≠ 𝑛,
which of the following is a distinguishing extension for 𝑥
and 𝑦?
a) 𝑧 = 0𝑛
b) 𝑧 = 1𝑛
c) 𝑧 = 10𝑛
d) 𝑧 = 01𝑛
2/17/2021 CS332 – Theory of Computation 3
Reusing a Proof
2/17/2021 CS332 – Theory of Computation 4
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 0s and 1s}
is not regular?
Using Closure Properties
2/17/2021 CS332 – Theory of Computation 5
𝐵 𝐶 𝐴∩ =
(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/17/2021 CS332 – Theory of Computation 6
Prove 𝐵 = {0𝑖1𝑗|𝑖 ≠ 𝑗} is not regular using
• nonregular language
𝐴 = 0𝑛1𝑛 𝑛 ≥ 0 and
• regular language
𝐶 = 𝑤 all 0s in 𝑤 appear before all 1s}
Which of the following expresses 𝐴 in terms of 𝐵
and 𝐶?
a) 𝐴 = 𝐵 ∩ 𝐶 c) 𝐴 = 𝐵 ∪ 𝐶
b) 𝐴 = ത𝐵 ∩ 𝐶 d) 𝐴 = ത𝐵 ∪ 𝐶
2/17/2021 CS332 – Theory of Computation 7
!DANGER!
2/17/2021 CS332 – Theory of Computation 8
Let 𝐵 = {0𝑖1𝑗|𝑖 ≠ 𝑗} and write 𝐵 = 𝐴 ∪ 𝐶 where
• nonregular language
𝐴 = 0𝑖1𝑗 𝑖 > 𝑗 ≥ 0 and
• nonregular language
𝐶 = 0𝑖1𝑗 𝑗 > 𝑖 ≥ 0 and
Does this let us conclude 𝐵 is nonregular?
Test 1 Topics
2/17/2021 CS332 – Theory of Computation 9
Sets, Strings, Languages (0)
• Know the definition of a string and of a language (and
the difference between them)
• Understand operations on strings: Concatenation,
reverse
• Understand operations on languages: Union,
intersection, concatenation, reverse, star, complement
• Know the difference between ∅ and 𝜀
2/17/2021 CS332 – Theory of Computation 10
Deterministic FAs (1.1)
• Given an English or formal description of a language 𝐿,
draw the state diagram of a DFA recognizing 𝐿 (and vice
versa)
• Know the formal definition of a DFA (A DFA is a 5
tuple…) and convert between state diagram and formal
description
• Know the formal definition of how a DFA computes
• Construction for closure of regular languages under
complement
2/17/2021 CS332 – Theory of Computation 11
Nondeterministic FAs (1.2)
• Given an English or formal description of a language 𝐿,
draw the state diagram of an NFA recognizing 𝐿 (and
vice versa)
• Know the formal definition of an NFA
• Know the power set construction for converting an NFA
to a DFA
• Proving closure properties: Know the constructions for
union, concatenation, star
• Know how to prove your own closure properties
2/17/2021 CS332 – Theory of Computation 12
Regular Expressions (1.3)
• Given an English or formal description of a language 𝐿,
construct a regex generating 𝐿 (and vice versa)
• Formal definition of a regex
• Know how to convert a regex to an NFA
• Know how to convert a DFA/NFA to a regex
2/17/2021 CS332 – Theory of Computation 13
Non-regular Languages (Myhill-Nerode Note)
• Understand the statements of the distinguishing set
method for proving DFA size lower bounds / non-
regularity
• Understand the proof of why the distinguishing set
method works, and be able to use it to prove similar
statements
• Know how to apply the method to specific languages
• Know how to show languages are non-regular by
combining distinguishing set method with closure
properties
2/17/2021 CS332 – Theory of Computation 14
Test tips
• You may cite without proof any result…
Stated in lecture
Stated and proved in the main body of the text (Ch. 0-1.4)
These include worked-out examples of state diagrams, regexes
• Not included above: homework problems, discussion
problems, (solved) exercises/problems in the text
• Showing your work / explaining your answers will help
us give you partial credit
• Make sure you’re interpreting quantifiers (for all / there
exists) correctly and in the correct order
2/17/2021 CS332 – Theory of Computation 15
Practice Problems
2/17/2021 CS332 – Theory of Computation 16
Name six operations under which the regular
languages are closed
2/17/2021 CS332 – Theory of Computation 17
Prove or disprove: All finite languages are
regular
2/17/2021 CS332 – Theory of Computation 18
Prove or disprove: The non-regular languages
are closed under union
2/17/2021 CS332 – Theory of Computation 19
Give the state diagram of an NFA recognizing
the language (01 U 10)*
2/17/2021 CS332 – Theory of Computation 20
Give an equivalent regular expression for the
following NFA
2/17/2021 CS332 – Theory of Computation 21
0,1
𝑞0 𝑞1
0
Is the following language regular?
{𝑎𝑛𝑎𝑛|𝑛 ≥ 0}
2/17/2021 CS332 – Theory of Computation 22
Is the following language regular?
{0𝑛1𝑛|0 ≤ 𝑛 ≤ 2021}
2/17/2021 CS332 – Theory of Computation 23
How many states does a DFA recognizing
0𝑛1𝑛 0 ≤ 𝑛 ≤ 2021 require?
2/17/2021 CS332 – Theory of Computation 24