Computer Science Department Logo
15-453 Formal Languages, Automata, and Computation
Main Page
  
Main Page 
 
Lecture Schedule, Notes and Readings
Assignments, Exams and Solutions
 Syllabus
Assignments
Grading and Policies
Textbook and Other Resources
Grading 
Reading 
Professor
Professor 
15-453 Course Syllabus
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.