15-453 - Formal Languages, Automata, and Computability

This course provides an introduction to formal languages, automata, computability, and complexity. The course consists of a traditional lecture component supported by weekly homework assignments and quizzes and a course project. There are two midterms and a final examination.

Topics

• Automata and Languages: finite automata, regular languages, pushdown automata, context-free languages, pumping lemmas.
• Computability Theory: Turing Machines, decidability, reducibility, the arithmetic hierarchy the recursion theorem, the Post correspondence problem.
• Complexity Theory: time complexity, classes P and NP, NP-completeness, space complexity, PSPACE, PSPACE-completeness, the polynomial hierarchy, randomized complexity, classes RP and BPP.

15-251 or 21-228.

Textbook: Introduction to the Theory of Computation (3rd Ed.) by Michael Sipser, 2012. Errata for 3rd Edition: http://math.mit.edu/~sipser/itoc-derrs3.1.html