| | | Lectures and Readings |
The schedule on the following page shows the tentative schedule of topics to be covered at each class meeting during the first half of the semester. The schedule for the second half of the term will be posted by the end of spring break.
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.
We expect you to do the reading for a class before the lecture. We 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. We will not attempt to cover in lecture all the material in the readings. Instead our 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, we encourage you to work in groups on these problems and 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 L stands for the on-line Haskell text by Lipovaca.
|
Lecture | Date | Topic | Reading | Practice Hmwk |
| 1. | Jan. 22 | Intro & Finite Automata | R 1 - 4, 5.1 - 5.3 | R 2.7, 4.4 |
| 2. | Jan. 24 | Non-deterministic finite automata | R 5.4 | R 5.2bc, 5.3, 5.5, 5.6bc |
| 3. | Jan 29 | Minimization | R 5.5 - 5.8 | R 5.8a, 5.11a |
| 4. | Jan. 31 | Regular expressions | R 6.1, 7 | 6.2bd |
| 5. | Feb. 5 | Regular expressions, grammars, & Pumping Lemma | R 8 | 7.1ab, 8.1abk |
| 6. | Feb. 7 | Decision Procedures for regular languages, Haskell | R 9, , LYAH 1 - 2 | 9.1ai |
| 7. | Feb. 12 | IO in Haskell | R 15.1 | 8.1abk |
| 8. | Feb. 14 | Modelling DFSM in Haskell | ||
| 9. | Feb. 19 | Regular Expressions in Haskell/Context-Free Grammars | R 11.1-11.8 | 11.5, 11.6df |
| 10. | Feb. 21 | Pushdown Automata | R 12.1 - 12.2 | 12.1cf, 11.5, 11.6df |
| 11. | Feb. 26 | Normal Forms & Pumping Lemma | R 12.3, 13.1- 13.3 | 12.2 |
| 12. | Feb. 28 | Closure for CFLs, Algorithms for CFLs | R 13.4-5, 14 | 13.1adf,14.1a |
| 13. | March 5 | Compilers: Parsing with Haskell | 15.2 | 13.17a |
| 14. | March 7 | More Parsing | ||
| 15. | March 12 | Turing Machines | R 17.1-17.2 | |
| 16. | March 14 | Turing Machine | R 17.3 | |
| March 18-22 | Spring Break | |||
| 17. | March 26 | Turing Machines Variants | R 17.3 | |
| 18. | March 28 | Universal Turing Machines | R 17.6 - 17.7 | |
| 19. | April 2 | UTMs, computabilty & Church-Turing Thesis | R 18 | |
| 20. | April 4 | Lambda Calculus | R18 | |
| 21. | April 9 | Formal Semantics | ||
| 22. | April 11 | PCF & Interpreters | ||
| 23. | April 16 | Type checking & Type inference | ||
| 24. | April 18 | Halting Problem | R19 | R21.1-21.3 |
| 25. | April 23 | Decidability, Semidecidability, Rice's Theorem | R20, 21.4-21.7 | |
|
26. | April 25 | Decidability of language problems | R22.5, and review ch. 9 & 14 | |
| 27. | April 30 | Unrestricted Grammars | ||
| 28. | May 2 | Godel Incompleteness | ||
|
29. | May 7 | Review & Summary | R21.5-21.7 | |
Rest of syllabus will be added later.
| | | Lectures and Readings |