HomeworkTopInstructor   TextsLectures and Readings

Lectures and Readings

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 three class days during the semester. I am planning on trying to schedule one class meeting outside of regular hours to make up for the material missed.

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. 23 Intro & Finite Automata R 1 - 4, 5.1 - 5.3 R 2.7, 4.4
2. Jan. 25 Non-deterministic finite automata R 5.4 R 5.2bc, 5.3, 5.5, 5.6bc
3. Jan. 28 Minimization R 5.5 - 5.8 R 5.8a, 5.11a
4. Jan. 30 Regular Expressions & Grammars R 6.1 6.2bd, 7.1ab
5. Feb. 1 Pumping Lemma & Decision Procedures R 8, 9 8.1abk, 9.1ai
6. Feb. 4 Context-free grammars R 11.1-11.8 11.5,11.6df
7. Feb. 6 Pushdown Automata R 12.1 - 12.2 12.1cf
8. Feb. 8 CFL-PDA Equivalence R 12.3 12.2
9. Feb. 11 Pumping Lemma & Closure for CFLs R 13.1 - 13.4 13.1adf
10. Feb. 13 Algorithms for CFLs R 14 14.1a
11. Feb. 15 Parsing 1 R 13.5, 15.1-2 13.17a
12. Feb. 18 Parsing & Propositional Logic HR 1.1, 1.3, 1.4.1
13. Feb. 20 Natural Deduction HR 1.2, 1.4.3 Prove modus tollens rule
14. Feb. 22 Soundness HR 1.4.3
15. Feb. 25 Completeness HR 1.4.4 Prove A, ¬B |- ¬(A -> B)
16. Feb. 27 Predicate Logic HR2.1 - 2.2
17. March 1 Proof Theory of Predicate Logic HR 2.3 HR 2.3.11a
18. March 4 Semantics of Predicate Logic HR 2.4-5 HR 2.4.5
19. March 6 Compactness & Expressivenesss HR 2.6 HR 2.5.1b
20. March 8 No class!
21. March 11 Extended Logics & Program Verification HR 4.1

22.

March 13 Program Verification HR 4.1-4.2
23. March 15 Hoare Logic HR 4.2-4.3 HR4.3.10
March 18-22 Spring Break
24. March 25 Intro to Model Checking HR 3.1-3.2
25. March 27 Model Checking HR 3.3, Emerson Model Checking
March 29 Chavez Day - no classes

26.

April 1 More Model Checking HR 3.3
27. April 3 Turing Machines R 17.1 - 17.2
28. April 5 TM Variants R 17.3
April 8 No Class - Out of town
29. April 10 Universal Turing Machine R 17.6 - 17.7
30. April 12 Church-Turing Thesis R 18
31. April 15 Halting Problem R 19
32. April 17 Decidability & Semidecidability R 20
April 19 No Class - Out of town
33. April 22 Reducibility R 21.1 - 21.3
34. April 24 Rice's Theorem R 21.4
35. April 26 Decidability of language problems R 9.14
36. April 29 More Undecidability R 21.5 - 21.7, 23.1-23.4
37. May 1 Recursion Theorem R 25
38. May 3 Godel Incompleteness R 25
39. May 6 Godel Incompleteness 2
40. May 8 Other formal systems


HomeworkTopInstructor   TextsLectures and Readings