Automata and Complexity

COURSE OBJECTIVE
The student is acquainted with important notions and algorithms regarding formal languages, automata, grammars, compilers, computability and complexity.

This course addresses foundational questions in computer science, such as: "What is a (programming) language?", "How can languages be recognised by computers (automata)", "Which problems can be solved using a class of automata?", "How much time and memory does solving a problem require?".

The course is divided into three parts: automata & languages, computability theory and quantum computing.

COURSE CONTENT
The first part, on automata and languages, deals with the concepts of formal language, grammar, and automaton. Two types of languages are covered: regular and context-free languages. Regular languages are used, e.g., in search queries, in the form of regular expressions. Context-free languages are suitable to describe programming languages. The automata-theoretic counterparts here are finite automata and the more powerful pushdown automata. Pumping lemmas are discussed to determine whether a language is regular or context-free. With each type of language a class of grammars is associated: left-linear and context-free grammars. Parsing algorithms are presented for context-free languages, to determine whether a string is in the language.

In the second part of the course, on computability theory, the central question is "Which computations can be performed on a computer?". To reason about this question, Turing machines are introduced, as well the Church-Turing thesis, along with examples of undecidable problems: the halting problem and the Post correspondence problem. It is shown how undecidability of new problems can be shown by reduction from a known undecidable problem. Important complexity classes from the complexity hierarchy are discussed, notably P, NP, and NP-complete, together with the corresponding reduction arguments.

The final part treats basic concepts in quantum computing: qubits, entanglement and quantum-operations. It is shown how quantum computing can improve computing, first using a parity game, and later by introducing Simon’s algorithm. The latter solves a problem in polynomial time, where in the traditional setting the best known solution has an exponential time complexity. We conclude with the quantum and probabilistic complexity classes BQP and BPP.

TEACHING METHODS
Lectures and seminars

TYPE OF ASSESSMENT
Written exam (plus weekly homework exercises, which can earn up to 0.5 bonus point)