Credits: 3 Level: graduate
Automata theory: deterministic and non-deterministic finite automata, pushdown automata, regular languages, context-free grammars, pumping lemma. Computability and recursion theory; Turing machines and their variations, decidability and recursive enumerability, mapping reducibility and Turing reducibility, undecidability of the halting problem, logical theories and Godel's incompleteness theorem. Complexity theory: time complexity, space complexity, major open problems on computational complexity.Prerequisites:
There are no prerequisites for this course.