Finite automata, formal languages, and regular expressions. Context free grammars and pushdown automata. Turing machines, Church’s thesis, complexity classes and (un)decidability.