CSCI 4325 · Fall 2026
Automata, Formal Languages, and Computation
Course information
- Section / CRN
- CSCI 4325.03 · 40296
- Class meetings
- Monday & Wednesday, 12:30–1:45 p.m.
- Classroom
- EIEAB 2.207
- Final exam
- Wednesday, December 9, 10:15 a.m.–noon
EIEAB 2.207
Instructor & office hours
- Instructor
- Austin Luchsinger
- Office
- EIEAB 3.246
- Office hours
- Tuesday & Thursday
9–11 a.m. and 2–4 p.m.
What can a computer compute?
Explore the mathematical foundations of computation, from finite automata and formal languages to Turing machines, computability, and complexity.
Textbook: Introduction to the Theory of Computation, Michael Sipser, 3rd edition.
Schedule & topics
Topics include finite-state machines, pushdown automata, formal grammars, Turing machines, the halting problem, and computational complexity.
| Week | Monday | Wednesday |
|---|---|---|
| 8/24 – 8/26 | No class | Intro |
| 8/31 – 9/2 | 3310 Review / DFA | DFA Quiz |
| 9/7 – 9/9 | Labor Day | DFA |
| 9/14 – 9/16 | DFA/NFA | DFA/NFA Exam |
| 9/21 – 9/23 | PDA | PDA Quiz |
| 9/28 – 9/30 | PDA | PDA Exam |
| 10/5 – 10/7 | Turing Machines | TM Quiz |
| 10/12 – 10/14 | Turing Machines | TM Exam |
| 10/19 – 10/21 | TBD | TBD |
| 10/26 – 10/28 | Decidability | Decidability Quiz |
| 11/2 – 11/4 | Decidability | Decidability Exam |
| 11/9 – 11/11 | Complexity 1 (membership) | Complexity 1 Quiz |
| 11/16 – 11/18 | Complexity 1 (membership) | Complexity 1 Exam |
| 11/23 – 11/25 | Complexity 2 (hardness) | Complexity 2 Quiz |
| 11/30 – 12/2 | Complexity 2 (hardness) | Complexity 2 Exam |
| 12/7 – 12/9 | No class | Final |
Review & extra credit
- The Imitation Game Extra credit materials.
Resources
Additional resources, courtesy of Dr. Wylie.
How to Prove It: A Structured Approach, Daniel Velleman, 2nd edition, 2006.
- Models of Computation Jeff Erickson, 2015.
- Introduction to Theory of Computation Anil Maheshwari and Michiel Smid, 2016.
- Lecture slides from MIT Ryan Williams, 2019.
- Lecture notes from MIT
- Mathematics and Computation Avi Wigderson, 2019.
- Introduction to Theoretical Computer Science Boaz Barak, 2020.
- Discrete Mathematics: An Open Introduction Oscar Levin, 3rd edition, 2020.