15453 Formal Languages, Automata, and Computation


Main
Page




Syllabus

Assignments



Grading

Reading


Professor


15453 Course Syllabus
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.
