Deterministic and nondeterministic automata, regular expressions, pumping lemmas; context-free languages, parsing, pushdown automata, context-sensitive languages, LBA, LR(k) languages, closure and decidability of language classes. Turing machines, random access machines, grammars, general recursive functions, equivalence of computation models, universal machines, relative computing. Unsolvability, semi-recursive sets, Rice's Theorem. Space and time complexity. NP completeness.