| Date | Topic | Reading |
|---|
| 1/5 | Review of proof techniques, intro. to
automata | 1, 2.1 |
| 1/10 | Deterministic and nondeterministic finite
automata | 2.2--2.4 | |
| 1/12 | Epsilon-NFA's, regular expressions | 2.5,
3.1--3.3 |
| 1/19 | Properties of regular languages |
3.4, 4.1, 4.2 |
| 1/24 | Algorithms for regular languages | 4.3,
4.4 |
| 1/26 | Context-free grammars | 5.1--5.3 |
| 1/31 | Ambiguous grammars, pushdown automata | 5.4,
6.1, 6.2 |
| 2/2 | PDA/CFG equivalence, deterministic PDA's | 6.3,
6.4 |
| 2/7 | Midterm | Through 2/2 lecture |
| 2/9 | Chomsky-normal-form grammars, pumping lemma | 7.1,
7.2 |
| 2/14 | Closure properties and algorithms for CFL's | 7.3,
7.4 |
| 2/16 | Introduction to Turing machines | 8.1--8.3 |
| 2/23 | Variations of Turing machines | 8.4,
8.5 |
| 2/28 | Decidability, recursive and RE languages | 9.1--9.3 |
| 3/1 | Some ``real'' undecidable problems | 9.4, 9.5 |
| 3/6 | P, NP, and an intractable problem | 10.1,
10.2 |
| 3/8 | NP-complete problems | 10.3, 10.4 |
