1. Introduction
2. Nondeterministic finite automata
3. Regular languages
4. Pumping lemma for regular languages
5. Context free grammars
6. Pushdown automata
7. Equivalence of PDAs and CFGs
8. Pumping lemma for CFLs
9. Introduction to Turing machines
10. Simulating other machines
11. Using Turing machines to solve hard problems
12. Using reductions to prove undecidability
13. Additional examples of reductions
14. Introspection and the recursion theorem
15. Undecidable problems in mathematical logic
16. NP Complete languages
17. Final words on chapter 7
18. Bottom-up parsing algorithms
19. Top-down parsing algorithms

1. Problems 1.6aj, 1.16b, 1.18j, 1.46a, 1.49 : due Friday, Sept. 24
2. Problems 2.4ce, 2.5ce, 2.44, 2.47: due Friday, Oct. 1
3. Problems 2.31, 2.48, 3.8b: due Friday, Oct. 8
4. Problems 3.13, 3.14, 3.15b, 3.19, 4.3, 4.11: due Monday, Oct. 18
5. Problems 5.9, 5.14, 5.23: due Wednesday, Oct. 27
6. Problems 6.6, 6.13: due Friday, Nov. 5
7. Problems 7.9, 7.12, 7.26, 7.27, 7.31: due Wednesday, Nov. 17

The first midterm exam is coming up on Wednesday, Oct. 13. Here are further details.

The second midterm exam is coming up on Wednesday, Nov. 3. Here are further details.

The final exam is coming up on Tuesday, Nov. 23. Here are further details.

Here is the final exam.

Syllabus

The syllabus for this course is here.

DirectMath

I strongly recommend that you use DirectMath software to write up your problem sets for this course. DirectMath is available as a free download at www.directmath.com.