Automata and Complexity

Vrije Universiteit Amsterdam

Course Description

  • Course Name

    Automata and Complexity

  • Host University

    Vrije Universiteit Amsterdam

  • Location

    Amsterdam, The Netherlands

  • Area of Study

    Computer Science

  • Language Level

    Taught In English

  • Course Level Recommendations


    ISA offers course level recommendations in an effort to facilitate the determination of course levels by credential evaluators.We advice each institution to have their own credentials evaluator make the final decision regrading course levels.

    Hours & Credits

  • ECTS Credits

  • Recommended U.S. Semester Credits
  • Recommended U.S. Quarter Units
  • Overview

    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.

    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.

    Lectures and seminars

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

Course Disclaimer

Courses and course hours of instruction are subject to change.

Some courses may require additional fees.


This site uses cookies to store information on your computer. Some are essential to make our site work; others help us improve the user experience. By using the site, you consent to the placement of these cookies.

Read our Privacy Policy to learn more.