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 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
| ||

Lectures and Readings |