Spring 2015

Carnegie Mellon University

A foundational course that introduces formal languages, automata, computability, and complexity theories, including finite automata, Turing machines, and P/NP classes.

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.

**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.

No data.

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

Lecture slides available at Schedule

No videos available

Assignments available at Assignments

No other materials available

Chomsky Normal FormContext-Free GrammarsCook-Levin TheoremDeterministic Finite AutomataEquivalence of PDAs and CFGsFixed-point theoremKarpKolmogorov complexityMapping ReducibilitiesMinimizing DFANP-completenessNon-Deterministic Turning MachinesNon-determinismOracle Turing MachinesP=NPPSPACE-CompletenessPolynomial TimePolynomial identity testingPost Correspondence ProblemPumping LemmaPumping lemma for context-free languagesPush-Down AutomataRecursion theoremReductionsRegular ExpressionsRegular LanguagesRegular OperationsRice’s TheoremSavitch's TheoremSpace ComplexityThe Arithmetic HierarchyTime ComplexityTuring MachinesTuring ReducibilityUndecidability