Formal Foundations 3

This module covers a branch of computer science called language and automata theory, focusing on concepts from computing theory and complexity theory. In particular, it discusses computation models (finite automata, regular expressions, pushdown automata, Turing machines), undecidability (what can be computed at all?), and intractability (how fast can it be computed?). The student will come to understand how these theories relate to, and are used in, everyday practice. Students learn concepts, tools, and techniques individually through a series of written exercises. There are weekly tutorial sessions with demonstrator support.