Theory of Computation

Mathematical preliminaries. Regular languages, regular expression, deterministic and non-deterministic finite automata, closure properties and pumping lemma. Context-free grammar and languages, pushdown automata and pumping lemma. Turing machines, the Church-Turing Thesis, Computability. Decidability and the Halting problem. Complexity, class P and NP.