15-453: Formal Languages, Automata, and Computation (FLAC)
Spring 2009 Semester
Computer Science Department


  • For more updates and announcements, see the Assignments page.
  • Final Exam: Tuesday, May 5, 5:30-8:30 PM, in Baker Hall 136A.
  • Project has been posted. See Assignments page.
  • The due date for the Bonus Problem of Homework 7 has been extended.
  • Midterm exam grade distribution. Note that there was a mistake in what was posted on the blackboard in class.
        100-102: 3
          95-99: 4
          90-94: 3
          85-89: 4
          80-84: 7
          75-79: 4
          70-74: 1
          65-69: 1
           0-60: 1 
  • Solutions to problems 4 and 6 of Homework 6 have been posted.
  • Solutions to Homeworks 4, 5, and parts of 6 have been posted. Some possible topics to be covered on the exam have been posted on the Assignments page.
  • Midterm Exam is on Tuesday, March 3, 2009. It is closed-book and closed-notes.
  • Homeworks 1, 2, 3, and 4 have been returned.
  • The book Introduction to Automata Theory, Languages, and Computation is on reserve in the Engineering library in Wean Hall.
  • Lecture notes on BDDs have now been posted.
  • If Denny is not in his office, you may slide your Homework 4 under his door.
  • HW 2 Grading Notes (Problem 4(c) was counted as an extra credit problem worth up to extra 8 points.)
  • The handout entitled "Lecture 15 Myhill-Nerode Relations" and "Lecture 16 The Myhill Nerode Theorem" contains all that you need to know to solve the Nerode homework problems.
  • Yi Wu has cancelled his office hours for Friday Feb 13.
  • Due date for Homework 4 has been changed.
  • For Problem 1 of Homework 3, you don't need to explicitly give a DFA; it would suffice to give an NFA and say something like "This NFA can be converted to a DFA using the standard construction".
  • A solution to the Extra Credit problem of Asgn 1, based on the method discussed in class, is now posted.
  • Mon Jan 12, 2009: Welcome to FLAC!

Course Description. 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. There is one midterm exam and a final exam.

Topics (tentative):

  • 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 and space complexity, classes P, NP, and PSPACE, NP-completeness, PSPACE-completeness, the polynomial hierarchy, randomized time complexity, classes RP and BPP.
Textbook: Introduction to the Theory of Computation (2nd Ed.) by Michael Sipser, 2005.

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

Grading and Homework


Tue and Thu, 1:30 -- 2:50 PM,  Wean Hall 5302

Contact Information

Professor: Edmund M. Clarke
Email: e​mc A​T c​s DOT cmu DOT e​du
Office: Wean Hall Rm 7117
Phone: (412) 268-2628   
Office hours: Immediately after class
Teaching Assistant: Will Klieber
Email: w​klieber A​T c​s DOT cmu DOT e​du
Office: Wean Hall Rm 3713
Phone: 412-268-5944
Office hours: Wed 12:30 pm -- 1:15 pm, and immediately after class
Teaching Assistant: Yi Wu
Email: y​iwu A​T c​s DOT cmu DOT e​du
Office: Wean Hall Rm 3713
Phone: 412-268-5944
Office hours: Friday 4:30 -- 5:30 pm (2/13 cancelled)
Course Secretary: Denny Marous
d​cm AT c​s DOT cmu DOT e​du
Office: Wean Hall Rm 7116
Phone: (412) 268-7660 Fax: (412) 268-5576
(Yes, both TAs are located in the same office.)