Introduction to the Theory of Computation

This note
explains the following topics: Automata and Language Theory, Finite automata,
regular expressions, push-down automata, context-free grammars, pumping
lemmas, Computability Theory, Turing machines, Church-Turing thesis,
decidability, halting problem, reducibility, recursion theorem, Complexity
Theory, Time and space measures, hierarchy theorems, complexity classes P, NP,
PSPACE, complete problems, P versus NP conjecture, quantifiers and games,
provably hard problems, probabilistic computation.

**Author(s):** Prof. Sofya Raskhodnikova

NA Pages