Automata and Complexity- Period 4

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.

Contact hours listed under a course description may vary due to the combination of lecture-based and independent work required for each course therefore, CEA's recommended credits are based on the ECTS credits assigned by VU Amsterdam. 1 ECTS equals 28 contact hours assigned by VU Amsterdam.