This is a preliminary outline of lecture topics and corresponding readings from the textbook. As the term progresses, we will correct it and add links to the handouts and slides from lecture. The board captures are of varying legibility and are offered primarily to remind you of which topics were discussed, so you can find and read the corresponding sections in the textbook.
| Week | Date | Lecture | Material covered | Board captures | Readings/Handouts/Hyperlinks | Comments |
|---|---|---|---|---|---|---|
| 1 | 1/16 | 1 | Administrivia, overview, motivation | 16jan lecture |
Chapter 0 | |
| 1/18 | 2 | More intro, strings and languages, intro to finite automata | 18jan lecture | Chapter 0, Section 1.1
Hangman |
Saturday is the Islamic New Year | |
| 2 | 1/23 | 3 | Formalizing DFAs, designing DFAs | 23jan lecture | Section 1.1 | |
| 1/25 | 4 | closure under union and complement, DFA minimization | 25jan lecture | Section 1.1 DFA minimization |
||
| 3 | 1/30 | 5 | NFA's, closure under three regular operations | 30jan lecture | Section 1.2 | Monday the 29th is add date |
| 2/1 | 6 | More examples of NFAs, equivalence of NFA's and DFA's | 1feb lecture | Section 1.2 | ||
| 4 | 2/6 | 7 | Removing epsilon transitions, regular expressions | 6feb lecture | Sections 1.2, 1.3 | |
| 2/8 | 8 | Regexs equivalent to NFAs/DFAs closure under homomorphism |
8feb lecture | Section 1.3 handout |
||
| 5 | 2/13 | Snow day | Wednesday is Valentine's Day | |||
| 2/15 | 9 | Proving languages non-regular (via pumping lemma, via closure properties) | 15feb lecture | Section 1.4
pumping lemma help closure properties | Sunday is Chinese New Year | |
| 6 | 2/20 | 10 | Uniqueness of minimal DFAs FSTs, statistical transition networks |
20 feb lecture | handout
patched example |
|
| 2/22 | first midterm 7-9pm 116 Roger Adams Lab lecture = review |
22 feb lecture | ||||
| 7 | 2/27 | 11 | Context-free grammars, parse trees, ambiguity, CNF | 27 feb lecture | Section 2.1 | |
| 3/1 | 12 | CNF conversion, pushdown automata | 1 march lecture | Section 2.2 Sheila Greibach (picture) Noam Chomsky Green Eggs and Ham grammar example 1965 computer |
||
| 8 | 3/6 | 13 | More examples of PDA's converting CFG's to PDA's |
6 mar lecture | Section 2.2 | |
| 3/8 | 14 | More examples of CFG-to-PDA conversion Converting PDAs to CFG's |
8 mar lecture | Section 2.2 | Drop date is Friday the 9th Daylight savings time ends on Sunday 11th |
|
| 9 | 3/13 | 15 | The pumping lemma for CFLs, closure properties | 13 Mar lecture | Section 2.3
closure properties |
|
| 3/15 | 16 | Turing machines | 15 Mar lecture | Section 3.1 Alan Turing Alonzo Church |
Saturday is St. Patrick's Day | |
| 3/20 | Playing on the beach | |||||
| 3/22 | Catching up on sleep | |||||
| 10 | 3/27 | 17 | Multi-tape TMs, encoding problems and decidability | 27 Mar lecture | Section 3.2 | |
| 3/29 | 18 | TM as interpreter, simulating a real computer |
29 Mar lecture | Section 3.3, Section 4.1 | ||
| 11 | 4/3 | Second midterm 7-9pm 1404 Siebel lecture = review |
Passover starts | |||
| 4/5 | 19 | Dynamic search and non-deterministic TM's | 5 Apr lecture | Sections 3.2, 4.1 | Sunday is Easter | |
| 12 | 4/10 | 20 | The Halting Problem and Undecidability | 10 Apr lecture | Section 4.2 | |
| 4/12 | 21 | Reductions for undecidability | 12 Apr lecture | Section 5.1 | ||
| 13 | 4/17 | 22 | Undecidable problems on linear bounded automata and CFLs | 17 Apr lecture | Section 5.1 | |
| 4/19 | 23 | More examples of reductions, Rice's theorem | 19 Apr lecture | Section 5.1 reduction help |
||
| 14 | 4/24 | 24 | Post's Correspondence problem, tiling problems, unknotting problem |
24 Apr lecture | Section 5.2 periodic tilings aperiodic tilings aperiodic wang tiles undecidability of tilings |
|
| 4/26 | 25 | Undecidability of CFG ambiguity Algorithms for automata |
26 Apr lecture | |||
| 15 | 5/1 | 26 | CYK parsing algorithm Course evals Recap, look ahead to other courses |
1 May lecture | May Day! | |
| 5/3 | no class: final on Saturday | Final Saturday 5/5, 1:30-4:30 |