Chapter pointers refer to the course textbook, M. Sipser, Introduction to the Theory of Computation. Reading assignments for future lectures are tentative, and they are provided in case you want to read ahead. In addition to the lecture notes and reading assignments from the textbook posted on this page, you should read also the lecture notes posted on the course main page
| Date | Topic | Reading/Notes |
|---|---|---|
| Fri, Sep 25 | Introduction | Ch. 0 |
| Mon, Sep 28 | DFAs | Ch. 1.1, notes on DFA |
| Wed, Sep 30 | Computations | Ch. 1.1 |
| Fri, Oct 2 | Closure properties | Ch. 1.2 |
| Mon, Oct 5 | NFAs | Ch. 1.2, notes on NFA |
| Wed, Oct 7 | Regular Operations | Ch. 1.2 |
| Fri, Oct 9 | Regular Expressions | Ch. 1.3 |
| Mon, Oct 12 | Equivalence of DFA and Regex | Ch. 1.3 |
| Wed, Oct 14 | Nonregular languages | notes on Diagonalization |
| Fri, Oct 16 | Pumping Lemma | Ch. 1.4 |
| Mon, Oct 19 | Review | Midterm 1 (7pm) |
| Wed, Oct 22 | Proving nonregular languages | All of Ch. 1 |
| Fri, Oct 23 | Finite State Transducers | notes on (N)FST |
| Mon, Oct 26 | Nondeterministic FST | NFST |
| Wed, Oct 28 | Context Free Grammars | Ch. 2.1 |
| Fri, Oct 30 | Review | |
| Mon, Nov 2 | More CFGs and ambiguity | Ch. 2.1 |
| Wed, Nov 4 | Non Context Free Languages | Ch. 2.3 and Diagonalization |
| Fri, Nov 6 | Push Down Automata | Ch. 2.2 |
| Mon, Nov 9 | Turing Machines | Ch. 3 |
| Fri, Nov 13 | Review | Midterm 2 (5pm) |
| Mon, Nov 16 | More on TM and Reductions | FST and mapping reductions |
| Wed, Nov 18 | Mapping reductions | Ch. 4.2, Ch. 5.3 |
| Fri, Nov 20 | Decidable Languages | Ch. 4.1 |
| Mon, Nov 23 | Undecidable Problems | Ch. 5.1 |
| Wed, Nov 25 | More undecidable Problems | Ch. 5.2 |
| Mon, Nov 30 | More undecidable Problems | |
| Wed, Dec 2 | Review | Ch 1-5 |
| Fri, Dec 4 | What’s next? | Ch. 7-8 |
| Wed, Dec 9 | Final Exam (7:00p-9:50p) |