BU CS 332 – Theory of Computation
Lecture 9:
• Midterm I review
Reading: Sipser Ch 0‐2.3
Mark Bun February 19, 2020
Midterm I Topics
2/19/2020 CS332 ‐ Theory of Computation 2
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
• Regular operations: Union, concatenation, star and closure of regular languages under regular operations, construction for closure under complement
• Cross‐product construction for union/intersection
2/19/2020 CS332 ‐ Theory of Computation 3
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
• Recall other closure properties: reverse, intersection, complement
2/19/2020 CS332 ‐ Theory of Computation 4
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/19/2020 CS332 ‐ Theory of Computation 5
Non‐regular Languages (1.4)
• Know the proof ideas for the pumping lemma for regular languages
• Understand the statement of the pumping lemma and how to apply it
• Beyond the pumping lemma: Showing languages are non‐regular by combining pumping lemma with closure properties
2/19/2020 CS332 ‐ Theory of Computation 6
Context‐free Grammars (2.1)
• Given an English or formal description of a language , give a CFG (in Backus‐Naur form) generating (and vice versa)
• Formal definition of a CFG (A CFG is a 4‐tuple…), context‐free languages
• Parse trees, derivations
• You are not responsible for the material on ambiguity in parsing and Chomsky Normal Form
But these are interesting! Read about them if you have time
2/19/2020 CS332 ‐ Theory of Computation 7
Pushdown Automata (2.2)
• Given an English or formal description of a language , describe a PDA recognizing in terms of:
• An algorithmic description of the machine • A state diagram for the machine
• (and vice versa)
• Formal definition of a PDA
• Know that PDAs recognize the context‐free languages.
You are not responsible for knowing the proof.
• Closure properties of CFLs: Regular operations and intersection with regular languages, but not complement or intersection
2/19/2020 CS332 ‐ Theory of Computation 8
Non‐context‐free Languages
• Know the proof ideas for the pumping lemma for CFLs
• Understand the statement of the pumping lemma and
how to apply it
• Beyond the pumping lemma: Showing languages are non‐context‐free by combining pumping lemma with closure properties
You are not responsible for Chapter 2.4 on deterministic CFLs (But read this if you’re interested in how CFLs are parsed in real compilers, etc.)
2/19/2020 CS332 ‐ Theory of Computation 9
Exam Tips
2/19/2020 CS332 ‐ Theory of Computation 10
Study Tips
• Review problems from HW 0‐3, discussion sections 1‐3, solved exercises/problems in Sipser, and suggested exercises on the homework
• We will literally ask you a question from the homework exercises, so make sure you understand these
• You may bring a page of notes to the exam. Preparing this note sheet is a great way to study.
2/19/2020 CS332 ‐ Theory of Computation 11
Study Tips
• Make sure you know how to solve the problems on the practice midterm and are familiar with the format. The format/length of the real midterm will be very similar.
• If you need more practice, there are lots of problems in the book. We’re happy to talk about any of these problems in office hours.
2/19/2020 CS332 ‐ Theory of Computation 12
For the exam itself
• You may cite without proof any result…
Stated in lecture
Stated and proved in the main body of the text (Ch. 0‐2.3)
These include worked‐out examples of state diagrams, regexes, CFGs, non‐regular/non‐CF languages
• Not included above: homework problems, discussion problems, (solved) exercise/problems in the text
• Showing your work / explaining your answers will help us give you partial credit
2/19/2020 CS332 ‐ Theory of Computation 13
Practice Problems
2/19/2020 CS332 ‐ Theory of Computation 14
2/19/2020 CS332 ‐ Theory of Computation 15
2/19/2020 CS332 ‐ Theory of Computation 16
2/19/2020 CS332 ‐ Theory of Computation 17
Regular Languages
2/19/2020 CS332 ‐ Theory of Computation 18
Name six operations under which the regular languages are closed
2/19/2020 CS332 ‐ Theory of Computation 19
Prove or disprove: The non‐regular languages are closed under union
2/19/2020 CS332 ‐ Theory of Computation 20
Give the state diagram of an NFA recognizing the language (01 U 10)*
2/19/2020 CS332 ‐ Theory of Computation 21
Give an equivalent regular expression for the
following NFA
0,1 001
2/19/2020 CS332 ‐ Theory of Computation 22
Give an equivalent regular expression for the
following NFA
0,1 001
2/19/2020 CS332 ‐ Theory of Computation 23
Let be a regular expression with symbols. If we convert into an NFA using the procedure described in class, how many states could it have in the worst case?
2/19/2020 CS332 ‐ Theory of Computation 24
Is the following language regular?
2/19/2020 CS332 ‐ Theory of Computation 25
Is the following language regular?
2/19/2020 CS332 ‐ Theory of Computation 26
Let∗ .
Let be a pumping length and 𝑝.
Give a decomposition of which can be pumped in . Is regular?
2/19/2020 CS332 ‐ Theory of Computation 27
Context‐Free Languages
2/19/2020 CS332 ‐ Theory of Computation 28
Name three operations under which the context‐free languages are closed.
Name two operations under which the CFLs are not closed
2/19/2020 CS332 ‐ Theory of Computation 29
What language is generated by the CFG
2/19/2020 CS332 ‐ Theory of Computation
30
?
What language is recognized by the following
PDA?
𝜀,𝜀 → $
0,𝜀→0 1,0→ 𝜀
2/19/2020
CS332 ‐ Theory of Computation
31
0
1
2
1,0→ 𝜀
𝜀, 0 → 𝜀
𝑓
Give a CFG for the language
2/19/2020 CS332 ‐ Theory of Computation 32
Give a PDA recognizing the language
2/19/2020 CS332 ‐ Theory of Computation 33
Prove that
∗
2/19/2020
CS332 ‐ Theory of Computation 34
is not context‐free