15453 Formal Languages, Automata, and Computation


Main
Page




Syllabus

Assignments



Grading

Reading


Professor


15453: Formal Languages, Automata, and Computation (FLAC)
Spring 2009 Semester
Computer Science Department 
Announcements
 For more updates and announcements, see the Assignments page.
 Final Exam: Tuesday, May 5, 5:308:30 PM, in Baker Hall 136A.
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, contextfree 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, NPcompleteness, PSPACEcompleteness, the polynomial hierarchy, randomized time complexity, classes RP and BPP.
Textbook: Introduction to the Theory of Computation (2nd Ed.) by Michael Sipser, 2005.
Prerequisites: 15212 and 15251 (or 21228).
Grading and Homework
Lectures
Tue and Thu, 1:30  2:50 PM, Wean Hall 5302
Contact Information
Professor:
Edmund M. Clarke
Email: emc AT cs DOT cmu DOT edu
Office: Wean Hall Rm 7117
Phone: (412) 2682628
Office hours: Immediately after class

Teaching Assistant:
Will Klieber
Email: wklieber AT cs DOT cmu DOT edu
Office: Wean Hall Rm 3713
Phone: 4122685944
Office hours: Wed 12:30 pm  1:15 pm, and immediately after class

Teaching Assistant:
Yi Wu
Email: yiwu AT cs DOT cmu DOT edu
Office: Wean Hall Rm 3713
Phone: 4122685944
Office hours: Friday 4:30  5:30 pm (2/13 cancelled)

Course Secretary:
Denny Marous
dcm AT cs DOT cmu DOT edu
Office: Wean Hall Rm 7116
Phone: (412) 2687660 Fax: (412) 2685576

(Yes, both TAs are located in the same office.)
