Karp

Regular Languages

Pumping Lemma

Pumping lemma for context-free languages

Undecidability

Rice’s Theorem

Turing Reducibility

Polynomial Time

Cook-Levin Theorem

Space Complexity

Regular Operations

Push-Down Automata

Chomsky Normal Form

Mapping Reducibilities

Fixed-point theorem

P=NP

Savitch's Theorem

Kolmogorov complexity

Non-determinism

Minimizing DFA

Equivalence of PDAs and CFGs

Reductions

Recursion theorem

The Arithmetic Hierarchy

Non-Deterministic Turning Machines

Polynomial identity testing

Deterministic Finite Automata

Regular Expressions

Context-Free Grammars

Turing Machines

Post Correspondence Problem

Oracle Turing Machines

Time Complexity

NP-completeness

PSPACE-Completeness

15-453 - Formal Languages, Automata, and Computability Carnegie Mellon University Spring 2015 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.

### 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

15-453 - Formal Languages, Automata, and Computability

Theoretical Computer Science

Karp (band)

Karp

1 courses cover this concept

15-453 - Formal Languages, Automata, and Computability