The course will follow the course text M. Sipser, Introduction to the Theory of Computation (PWS, Boston 1997)

Mathematical preliminaries; regular languages, finite automata, and regular expressions; nondeterminism and determinism in finite automata; properties of regular languages; nonregular languages; context-free languages, context-free grammars, and pushdown automata; nondeterminism and determinism in pushdown automata; properties of context-free languages; non-context-free languages; multi-stack machines; recursively-enumerable languages and Turing machines; recursive and nonrecursive languages; reductions.