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. It is probably a little over-ambitious and I have scheduled optional topics for the last few classes that can be dropped if necessary. 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 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. 18 | Intro & Finite Automata | R 1 - 4, 5.1 - 5.3 | R 2.7, 4.4 |

2. | Jan. 20 | Non-deterministic finite automata | R 5.4 | R 5.2bc, 5.3, 5.5, 5.6bc |

3. | Jan. 23 | Minimization | R 5.5 - 5.8 | R 5.8a, 5.11a |

4. | Jan. 25 | Regular Expressions & Grammars | R 6.1 | 6.2bd, 7.1ab |

5. | Jan. 27 | Pumping Lemma & Decision Procedures | R 8, 9 | 8.1abk, 9.1ai |

6. | Jan. 30 | Context-free grammars | R 11.1-11.8 | 11.5,11.6df |

7. | Feb. 1 | Pushdown Automata | R 12.1 - 12.2 | 12.1cf |

8. | Feb. 3 | CFL-PDA Equivalence | R 12.3 | 12.2 |

9. | Feb. 6 | Pumping Lemma & Closure for CFLs | R 13.1 - 13.4 | 13.1adf |

10. | Feb. 8 | Algorithms for CFLs | R 14 | 14.1a |

11. | Feb. 10 | Parsing 1 | R 13.5, 15.1-2 | 13.17a |

12. | Feb. 13 | Parsing & Propositional Logic | HR 1.1, 1.3, 1.4.1 | |

13. | Feb. 15 | Natural Deduction | HR 1.2, 1.4.3 | Prove modus tollens rule |

14. | Feb. 17 | Soundness | HR 1.4.3 | |

15. | Feb. 20 | Completeness | HR 1.4.4 | Prove A, not-B |- not(A -> B) |

16. | Feb. 22 | Predicate Logic | HR2.1 - 2.2 | |

17. | Feb. 24 | Proof Theory of Predicate Logic | HR 2.3 | HR 2.3.11a |

18. | Feb. 27 | Semantics of Predicate Logic | HR 2.4 | HR 2.4.5 |

19. | Feb. 29 | Semantics & Models | HR 2.5 | HR 2.5.1b |

20. | March 2 | Soundness & Completeness | ||

21. | March 5 | Compactness & Expressiveness | HR 2.6 | |

22. | March 7 | Program Verification | HR 4.1-4.2 | |

23. | March 9 | Hoare Logic | HR 4.2-4.3 | HR4.3.10 |

March 12-16 | Spring Break
| |||

24. | March 19 | Intro to Model Checking | HR 3.1-3.2 | |

25. | March 21 | Model Checking | HR 3.3, Emerson Model Checking | |

26. | March 23 | More Model Checking | HR 3.3 | |

27. | March 26 | Turing Machines | R 17.1 - 17.2 | |

28. | March 28 | TM Variants | R 17.3 | |

March 30 | Chavez Day - no classes
| |||

April 2 | No Class - Out of town
| |||

29. | April 4 | Universal Turing Machine | R 17.6 - 17.7 | |

30. | April 6 | Church-Turing Thesis | R 18 | |

31. | April 9 | Halting Problem | R 19 | |

32. | April 11 | Decidability & Semidecidability | R 20 | |

33. | April 13 | Reducibility | R 21.1 - 21.3 | |

34. | April 16 | Rice's Theorem | R 21.4 | |

35. | April 18 | Decidability of language problems | R 9.14 | |

36. | April 20 | More Undecidability | R 21.5 - 21.7 | |

37. | April 23 | Grammars equiv to TMs | R 23.1-23.4 | |

38. | April 25 | Recursion Theorem | R 25 | |

39. | April 27 | Godel Incompleteness | ||

40. | April 30 | Other formal systems | ||

41. | May 2 | No class | ||

Lectures and Readings |