Lecture Notes

1. Intro and First Lecture
   • Introduction
   • Chapter 0
   • Section 1.1
2. Section 1.2
   • NFAs
   • Regular Operations
3. Regular Expressions
4. Pumping Lemma
5. DFA Minimization
   • Sudkamp Excerpt
   • Notes
6. Context Free Grammars
   • Part I
   • Part II
7. Pushdown Automatas
8. Pumping Lemma for Context Free Languages
9. Exam #1 Review
10. Turing Machines
    • Intro to TMs
    • Drew, Anthony, Chris and Sean's Notes
11. Turing Machine Variants
12. Recursively Enumerable Languages
13. Halting Problem
14. Parsing
15. Greibach Normal Form and DFA Minimization
    • Greibach Normal Form
16. Reducibility
17. Mapping Reducibility
18. Exam #2 Review
19. The Class P
20. The Class NP
21. Polynomial-Time Reducibility
    • Version 1
    • Version 2
22. Proof of Cook-Levin Theorem
    • Version 1
    • Version 2
23. Final Exam Review