15-453 Formal Languages, Automata and Computation
Spring 2014, TTH 12:00-1:20, GHC 4215

[Schedule/Assignments | Project Info | What's New?]

 

Instructor:

Lenore Blum (lblum@cs), Gates 7105. 
Office Hours: Tuesday 2-3pm, Gates 7105
 
TAs: 
Asa Frank (afrank@andrew.cmu.edu)
Office Hours: Friday, 5:30-7:30pm, GHC 6002
 
Aashish Jindia (ajindia@andrew)
Office Hours: Sunday, 6-8pm, Wean 5316
 
Andrew Smith (adsmith@andrew)
Office Hours: Monday 5:45-7:45pm, Room GHC 7101


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 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 PPACE, PSPACE-completeness, the polynomial hierarchy, randomized complexity, classes RP and BPP.


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


Prerequisites: 15-251 (or 21-228).

Grading: Homework, 25%; Class Participation, 5%; Midterm I, 15%; Midterm II, 15%; Final, 25%; Project 15%. Attendance is required.

Homework: Homework is due one week after it is assigned and should be handed in at the beginning of class. Late homework will be accepted only under exceptional circumstances. All assignments must be typeset (exceptions allowed for diagrams). Each problem should be done on a separate page.

Each student is to do their own work and hand in their own homework individually. Collaboration is allowed, but References used (including books, articles, websites, people, including yourself) must be listed!

Project: See Project Info.

© 2014 Carnegie Mellon University, all rights reserved.