This is a preliminary outline of lecture topics and corresponding readings from the textbook. Right now, the topic details still reflect what was taught last term. As the term progresses, we will update it for what we actually covered and add links to the handouts and slides from lecture.
Lecture notes are intended only to show what topics were covered, so you can find and read the corresponding sections in the textbook. They are not intended to be a substitute for the textbook and handouts.
Review of most material in the course.
| Lecture Number | Date | Material covered | Lecture notes | Readings/Handouts/Hyperlinks | Comments |
|---|---|---|---|---|---|
| 1 | 1/15 | Administrivia, overview, motivation | lecture 1 | Chapter 0 | |
| disc 1 | 1/16 | Discrete math review intro to strings |
discussion 1 | Chapter 0 Extra notes: Discrete Mathematics, by Chen Read Chap. 1, 2 and 3 (20 pgs). | |
| 2 | 1/17 | Strings and languages intro to DFAs |
Lecture 2 | Section 1.1 | |
| 3 | 1/22 | JFLAP demo formal definitions for DFAs FSTs closure under complement |
Lecture 3 | Section 1.1 JFLAP |
Monday is MLK day |
| disc 2 | 1/23 | DFA examples | discussion 2 | Section 1.1 | |
| 4 | 1/24 |
regular expressions closure under union, intersection |
Lecture 4 | Sections 1.1, 1.3 | |
| 5 | 1/29 | NFA's | Lecture 5 | Section 1.2 | |
| disc 3 | 1/30 | NFA examples | Discussion 3 | Section 1.2 | |
| 6 | 1/31 |
closure under three regular operations string reversal, homomorphism regex to NFA | Lecture 6 | Sections 1.2, 1.3
closure properties |
7 | 2/5 | Equivalence of NFA's and DFA's | Lecture 7 | Section 1.2 | Election Lent starts Wed |
| disc 4 | 2/6 | Quiz 1
Subset construction Epsilon transitions |
Discussion 4 | Section 1.2 | |
| 8 | 2/7 | Regular expressions equivalent to NFAs/DFAs | Lecture 8 | Section 1.3 | Chinese New Year |
| 9 | 2/12 | Proving languages non-regular | Lecture 9 | Section 1.4
pumping lemma help |
Monday is Vasant Panchami |
| disc 5 | 2/13 | Pumping lemma examples | Discussion 5 | Section 1.4 | |
| 10 | 2/14 | Suffix languages DFA minimization |
Lecture 10 | [see lecture notes] | Valentine's Day |
| 2/19 | First midterm 7-9pm lecture = review |
||||
| disc 6 | 2/20 | Proofs using closure properties | Discussion 6 | ||
| 11 | 2/21 | Context-free grammars, parse trees, ambiguity | Lecture 11 | Section 2.1
The Groke grammar example Green Eggs and Ham |
|
| 12 | 2/26 | pushdown automata | Lecture 12 | Section 2.2 | Passover starts on Saturday |
| disc 7 | 2/27 | Context-free grammar and PDA examples | Discussion 7 | ||
| 13 | 2/28 | closure properties CFG to PDA conversion |
Lecture 13 | Section 2.2
closure properties |
|
| 14 | 3/4 | PDA to CFG conversion | Lecture 14 | Section 2.2 | |
| disc 8 | 3/5 | Quiz 2 PDA/CFG conversion examples |
discussion 8 | ||
| 15 | 3/6 | Chomsky-normal form | Lecture 15 | Section 2.2 Sheila Greibach (picture) Noam Chomsky 1965 computer |
Friday is drop date |
| 16 | 3/11 |
The pumping lemma for CFLs non-closure facts |
Lecture 16 | Section 2.3 | |
| disc 9 | 3/12 |
CNF conversion non-regularity proofs w/closure properties |
discussion 9 | ||
| 17 | 3/13 | Turing machines | Lecture 17 | Section 3.1 Alan Turing Alonzo Church |
|
| 3/18 | Fighting and waiting through crowded airports | Spring break | |||
| 3/20 | Playing in the sun | Spring break Muhammad's Birthday Sunday is Easter |
|||
| 18 | 3/25 |
More TM examples Multi-tape TMs |
Lecture 18 | Section 3.2 | |
| disc 10 | 3/26 | Preparing for the second midterm | discussion 10 | ||
| 3/27 | Second midterm 7-9pm lecture = review |
||||
| 19 | 4/1 | Encoding problems, decidability | Lecture 19 | Section 3.3, 4.1 | April Fool's Day! |
| disc 11 | 4/2 | TM design examples | discussion 11 | ||
| 20 | 4/3 |
TM as interpreter, simulating a real computer, more decidable problems |
Lecture 20 | Section 4.1 | |
| 21 | 4/8 | The Halting Problem and Undecidability | Lecture 21 | Section 4.2 | |
| disc 12 | 4/9 | Help! The Halting problem blew out my brain! | discussion 12 | ||
| 22 | 4/10 | Reductions for undecidability | Lecture 22 | Section 5.1 reduction help |
|
| 23 | 4/15 | Rice's Theorem | Lecture 23 | Section 5.1 | Monday is Hindu New Year |
| disc 13 | 4/16 | Examples of reductions | discussion 13 | ||
| 24 | 4/17 |
Undecidable problems on linear bounded automata and CFLs |
Lecture 24 | Sections 5.1 | |
| 25 | 4/22 |
Dovetailing Enumeration and decidability Non-deterministic TM's |
Lecture 25 | Section 3.2 | |
| disc 14 | 4/23 | Quiz 3 Dovetailing |
discussion 14 | ||
| 26 | 4/22 | Post's Correspondence problem Undecidability of CFG ambiguity tiling problems |
Lecture 26 | Section 5.2 periodic tilings aperiodic tilings aperiodic wang tiles Penrose tilings undecidability of tilings |
|
| 27 | 4/29 | CYK parsing algorithm Course evals |
Lecture 27 | Review handout | |
| disc 15 | 4/30 | Review for final | |||
| 5/1 | reading day: no class | May Day | |||
| 5/6 | exam week: no class | Monday is Cinco de Mayo | |||
| 5/8 | exam week: no class |