The schedule on the following two pages shows the tentative schedule of topics to be covered at each class meeting during the semester. I will be out of town at least one day during the semester.

Consult this page regularly to see the most current version of the schedule of topics and readings. The on-line version of this schedule will be revised and kept up-to-date as the semester progresses.

I expect you to do the reading for a class before the lecture. I chose the texts for this course as being a bit easier than usual to read (at least for this material). You will find lots of examples and discussion of the material in the text. I will not attempt to cover in lecture all the material in the readings. Instead my goal will be to cover the highlights or particularly difficult material, some of which won't be in the text. For this to work, you will need to already be familiar with the simpler aspects of the material. If you keep up your part of the bargain we should be able to have more interesting discussions in class, rather than just listening to me go over the text.

The practice homework listed with each lecture is to be done after the corresponding lecture. It is there to help you test your understanding of the course material and to help prepare you for the weekly homework assignment. The practice homework will not be turned in. However, I encourage you to ask questions about it at the beginning of the next class. Homework of the form n.m means problem m from chapter n.

In the table below, R stands for the Automata textbook by Rich, while HR stands for the logic text by Huth and Ryan.

 Lecture Date Topic Reading Practice Hmwk 1. Jan. 21 Intro & Finite Automata R 1 - 4, 5.1 - 5.3 R 2.7, 4.4 2. Jan. 23 Non-deterministic finite automata R 5.4 R 5.2bc, 5.3, 5.5, 5.6bc 3. Jan 26 No class! 4. Jan. 28 Minimization R 5.5 - 5.8 R 5.8a, 5.11a 5. Jan. 30 Regular Expressions & Grammars R 6.1 6.2bd, 7.1ab 6. Feb. 2 Back to minimization R 8, 9 8.1abk, 9.1ai 7. Feb. 4 Context-free grammars R 11.1-11.8 11.5,11.6df 8. Feb. 6 Pumping Lemma & Decision Procedures for regular languages R 8, 9 8.1abk, 9.1ai 9. Feb. 9 Pushdown Automata R 12.1 - 12.2 12.1cf 10. Feb. 11 Normal Forms & Pumping Lemma R 12.3 12.2 11. Feb. 13 Pumping Lemma & Closure for CFLs R 13.1 - 13.4 13.1adf 12. Feb. 16 Algorithms for CFLs R 14 14.1a 13. Feb. 18 Parsing 1 R 13.5, 15.1-2 13.17a 14. Feb. 20 Parsing & Propositional Logic HR 1.1, 1.3, 1.4.1 15. Feb. 23 Natural Deduction HR 1.2, 1.4.3 Prove modus tollens rule 16. Feb. 25 Soundness HR 1.4.3 17. Feb. 27 Completeness HR 1.4.4 Prove A, ¬B |- ¬(A -> B) 18. March 2 Predicate Logic HR2.1 - 2.2 19. March 4 Proof Theory of Predicate Logic HR 2.3 HR 2.3.11a 20. March 6 Semantics of Predicate Logic HR 2.4-5 HR 2.4.5 21. March 9 Completeness & Compactness HR 2.6 HR 2.5.1b 22. March 11 Extended Logics & Program Verification HR 4.1 23. March 13 Program Verification HR 4.1-4.2 March 16-20 Spring Break 24. March 23 Hoare Logic HR 4.2-4.3 HR4.3.10 25. March 25 Intro to Model Checking HR 3.1-3.2 March 27 Chavez Day - no classes 26. March 30 Model Checking HR 3.3, Emerson Model Checking 27. April 1 More Model Checking HR 3.4-5 28. April 3 Turing Machines R 17.1 - 17.2 29 April 6 TM Variants R 17.3 30. April 8 Universal Turing Machine R 17.6 - 17.7 31. April 10 Church-Turing Thesis R 18 32. April 13 Halting Problem R 19 33. April 15 Decidability & Semidecidability R 20 34. April 17 Reducibility & Rice's theorem Video of lecture Part 1, Part 2 34. April 20 Rice's Theorem R 21.1 - 21.7 35. April 22 Type 0 grammars R 23.1-4 36. April 24 Computable Functions R 25.1-2 37. April 27 Godel Incompleteness R 25.3 (just skim) 38. April 29 Godel Incompleteness 2 39. May 1 History & Review 40. May 4 no class 41. May 6 no class