Here is this semester's tentative schedule; we will update it as the semester progresses. The readings refer to relevant parts of the course textbook by Sipser and the Spring 2008 lecture notes prepared by Margaret Fleck and Sariel Har-Peled.Disclaimer: Please note that the reading references are not substitutes for attending lecture; they simply provide a rough outline of topics discussed in class and may not be complete.
Date Topic Reading Note M Jun 09 Course intro Chapter 0; sp08-lec02. HW1 out T Jun 10 Deterministic Finite Automata (DFAs) Chapter 1.1; sp08-lec03. W Jun 11 Regular Languages; Closure Properties; Intro to NFAs Finish Ch. 1.1, Start Ch 1.2; sp08-lec05 R Jun 12 NFAs; Equivalence of NFAs and DFAs Ch 1.2; sp08-lec07 F Jun 13 Recitation recitation 1 M Jun 16 Regular expressions Start Ch 1.3; sp08-lec04 HW1 due, HW2 out T Jun 17 Equivalence of regular expressions and NFAs/DFAs Ch 1.3; sp08-lec08 W Jun 18 Limitations of regular languages Start Ch 1.4; sp08-lec09 R Jun 19 Pumping lemma and proving non-regularity Ch 1.4; sp08-lec09 F Jun 20 Recitation recitation 2 HW1 rev due M Jun 23 Proving non-regularity via closure properties; examples of deciding whether a given language is regular or not. Ch 1.4; Exercise 1.54 HW2 due, HW3 out T Jun 24 Myhill-Nerode theorem Exercise 1.52; sp08-lec10 W Jun 25 MIDTERM 1 - IN CLASS R Jun 26 Minimizing DFAs sp08-lec10 F Jun 27 Recitation recitation 3 HW2 rev due M Jun 30 Context-free grammars Ch 2.1; sp08-lec11; Lsystem demo HW3 due, HW4 out T Jul 01 Chomsky normal form Ch 2.1; sp08-lec15 W Jul 02 Converting to CNF; CYK parsing algorithm Ch 2.1; sp08-lec15 R Jul 03 Pumping lemma for CFLs Ch 2.3; sp08-lec16 HW3 rev due F Jul 04 NO CLASS M Jul 07 Introduction to PDAs Start Ch 2.2; sp08-lec12 HW4 due, HW5 out T Jul 08 Formal definition of a PDA; Closure properties and Non-closure facts for CFLs Ch 2.2; sp08-lec13; sp08 closure property handout W Jul 09 Conversions: CFG to GPDA to PDA to NPDA Ch 2.2; sp08-lec13; start sp08-lec14 R Jul 10 Conversions: NPDA to CFG Ch 2.2; sp08-lec14 F Jul 11 Recitation recitation 4 HW4 rev due M Jul 14 Turing machines, examples Ch 3.1; sp08-lec17, sp08-lec18 HW5 due, HW6 out T Jul 15 More TM examples, TM variants Ch 3.2; sp08-lec18 W Jul 16 MIDTERM 2 - IN CLASS R Jul 17 Closure properties, enumerators Ch 3.2, 3.3 F Jul 18 Recitation recitation 5 HW5 rev due M Jul 21 Decidable properties of languages Ch 4.1 HW6 due, HW7 out T Jul 22 Diagonalization; ATM is undecidable Ch 4.2; sp08-lec21 W Jul 23 Reductions I Start Ch 5.1; sp08-lec22 R Jul 24 Reductions II; Rice's Theorem Finish Ch 5.1; sp08-lec23 F Jul 25 Recitation recitation 6 HW6 rev due M Jul 28 Linear bounded automata Ch 5.1; sp08-lec24 HW7 due T Jul 29 Undecidable properties of CFL; computation histories Ch 5.1; sp08-lec24 W Jul 30 Post correspondence problem Ch 5.2; sp08-lec26 R Jul 31 Recitation (Review of Reductions) recitation 7 HW7 rev due Aug 2 FINAL EXAM at 1pm