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 | ||
Lectures and Readings |