Lec Date Subject Reading Homework
assigned due
1 8/31 Introduction, terminology, definitions 1.1,7.1 HW1
2. 9/2 Continued Introduction and Overview 2.1
9/7 Labor Day Holiday
3. 9/9 Finite Automata and Regular Expresions 2.2 HW2 HW1
4. 9/14 Nondeterministic Finite Automata 2.3
5. 9/16 Epsilon moves 2.4 HW3 HW2
6. 9/21 Constructions 2.5
7. 9/23 Moore and Mealy machines 2.7 HW4 HW3
8. 9/28 Pumping lemma for regular sets 3.1
9. 9/30 Regular set properties 3.2 study HW4
10. 10/5 Decision algorithms for regular sets 3.3
11. 10/7 Quiz 1 HW5
12. 10/12 Myhill-Nerode Theorem 3.4
13. 10/14 Context Free Grammars 4.1,4.2 HW6 HW5
14. 10/19 CFG derivation trees 4.3
15. 10/21 CFG simplification algorithm 4.4 HW6
16. 10/26 Chomsky normal form 4.5
17. 10/28 Greibach normal form 4.6 project
18. 11/2 Inherently ambiguous CFL's 4.7
19. 11/4 Quiz 2 HW7
20. 11/9 Pushdown Automata 5.1,5.2
21. 11/11 More Pushdown Automata 5.2,5.3 HW8 HW7
22. 11/16 NPDA and CFL 5.3
23. 11/18 CYK algorithm 6.3 HW8
24. 11/23 CFL pumping lemma 6.1
25. 11/25 CFL properties 6.2 HW9 project
26. 11/30 Turing machine model 7.1,7.2
27. 12/2 Turing machine - language, construction 7.3,7.4 HW10 HW9
28. 12/7 Church Turing Thesis 7.5,7.6
29. 12/9 Review HW10
30. 12/16 Final Exam 6:00 - 8:00 (no other) all late homework due.
Last updated 11/30/98