Microsoft PowerPoint – CS332-Lec08-ann
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 . For and , ,
which of the following is a distinguishing extension for
and ?
a)
b)
c)
d)
2/17/2021 CS332 ‐ Theory of Computation 2
Mea Culpa
What I meant to write:
Let and consider the distinguishing
set . For and , ,
which of the following is a distinguishing extension for
and ?
a)
b)
c)
d)
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 s and s
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 is not regular using
• nonregular language
and
• regular language
all s in appear before all s
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 and write where
• nonregular language
and
• nonregular language
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?
2/17/2021 CS332 ‐ Theory of Computation 22
Is the following language regular?
2/17/2021 CS332 ‐ Theory of Computation 23
How many states does a DFA recognizing
require?
2/17/2021 CS332 ‐ Theory of Computation 24
2/17/2021 CS332 ‐ Theory of Computation 25
2/17/2021 CS332 ‐ Theory of Computation 26
2/17/2021 CS332 ‐ Theory of Computation 27