Formal Languages and Automata

CSC448/CSC2405, Fall 2021

Course Info

Instructor: Swastik Kopparty (
Class Time and Place: Wednesdays 1pm-3pm, Bahen 1240 (and Zoom)
Office Hours: Wednesdays 11am-12noon (on Zoom)
TA: Harry Sha
Tutorials: Friday 1pm-2pm, Bahen 1240 (and Zoom)
TA Office hours: Mondays 4:30pm-5:30pm (on Zoom)

Please use the course piazza site for questions.

Text book: Introduction to the Theory of Computation, 3rd Edition (by Sipser).

Please email me if you are not enrolled in the course and would like to sit in. Please email me if you are trying to enroll in the course and would like to be added to the course quercus site in the meantime.

This course will study primitive (and beyond) mathematical models for computers, and how to understand the power and limitations of these models. Topics include: Regular Languages, Finite Automata, Regular Expressions, Context-Free Languages, Context-Free Grammars, Pushdown Automata, Computability Theory, Turing Machines, Undecidability and a taste of Computational Complexity Theory. This course will need comfort with proofs and mathematical precision.

Syllabus and course policies
Rough course outline: