CS代考计算机代写 algorithm compiler BU CS 332 – Theory of Computation

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/18/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/18/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/18/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/18/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/18/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/18/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/18/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/18/2020 CS332 – Theory of Computation 9

Exam Tips
2/18/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/18/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/18/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/18/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

2/19/2020 CS332 – Theory of Computation 18

2/19/2020 CS332 – Theory of Computation 19

Regular Languages
2/18/2020 CS332 – Theory of Computation 20

Name six operations under which the regular languages are closed
2/19/2020 CS332 – Theory of Computation 21

Prove or disprove: The non-regular languages are closed under union
2/19/2020 CS332 – Theory of Computation 22

Give the state diagram of an NFA recognizing the language (01 U 10)*
2/19/2020 CS332 – Theory of Computation 23

Give an equivalent regular expression for the
following NFA
0,1
0
𝑞0
𝑞1
2/19/2020 CS332 – Theory of Computation
24

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 25

Is the following language regular?
{𝑎𝑛𝑎𝑛|𝑛 ≥ 0}
2/18/2020 CS332 – Theory of Computation 26

Is the following language regular?
{0𝑛1𝑛|0 ≤ 𝑛 ≤ 2020}
2/19/2020 CS332 – Theory of Computation 27

Let𝐿 = 𝑤∈ 0,1 ∗ 𝑤hasthesamenumberof0sand1s}. Let 𝑝 be a pumping length and 𝑠 = (01)𝑝.
Give a decomposition of 𝑠 = 𝑥𝑦𝑧 which can be pumped in 𝐿. Is 𝐿 regular?
2/19/2020 CS332 – Theory of Computation 28

Context-Free Languages
2/18/2020 CS332 – Theory of Computation 29

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 30

What language is generated by the CFG
𝑆→𝑎𝑆𝑏 𝑏𝑌 𝑌𝑎 Y→𝑏𝑌|𝑎𝑌|𝜀 ?
2/19/2020 CS332 – Theory of Computation 31

What language is recognized by the following
PDA?
𝑞0
𝜀,𝜀→$ 𝑞1,0→𝜀 1
0,𝜀→0 1,0→ 𝜀
𝜀, 0 → 𝜀
𝑞2
𝑞𝑓
2/19/2020
CS332 – Theory of Computation
32

Give a CFG for the language
𝑤#0𝑛 𝑛≥0,𝑤=𝑛}
2/18/2020 CS332 – Theory of Computation 33

Give a PDA recognizing the language
0𝑛1𝑛 𝑛 ≥ 0}
2/18/2020 CS332 – Theory of Computation 34

Prove that 𝑤 ∈ 0,1 ∗ 𝑤 is a palindrome with the same number of 0s and 1s} is not context-free
2/19/2020 CS332 – Theory of Computation 35