Catalog Description
Finite automata, regular sets, pushdown automata, context-free grammars. Turing machines, recursive functions and undecidability. Prerequisite: MATH 241 or MATH 280.
Schedule
| Section | Time | Location |
|---|---|---|
| Lecture | MWF 2-2:50PM | Dana 227 |
| Recitation | Th 3-3:50PM | Dana 303 |
Syllabus
Lecture Notes
- Set 1 – Intro
- Set 2 – Math Review
- Set 3 – Intro to Automata
- Set 4 – NFAs
- Set 5 – DFA/NFA Equivlance, Closure Properties
- Set 6 – Regular Expressions
- Set 7 – Pumping Lemma
- Exam 1 Study Guide
- Set 8 – Context-Free Grammars
- Set 9 – Chomsky Normal Form
- Set 10 – Pushdown Automata
- Set 11 – Context-Free Languages Pumping Lemma
- Set 12 – Turing Machines
- Set 13 – Modified Turing Machines
- Exam 2 Study Guide
- Set 14 – Decidability
- Set 15 – Undecidability, Infinity
- Set 16 – Reductions
These notes closely follow Michael Sipser’s Introduction to the Theory of Computation. I was also influenced by my notes from taking Prasad Jayanti’s course at Dartmouth College and notes from Zack Scherr at Bucknell University.
If you want to use these notes for your own course, please just let me know! I’m also happy to share LaTeX source if that would be helpful.