Automata and Complexity

Periode 4
Faculteit der Exacte Wetenschappen
drs. J. Endrullis
drs. J. Endrullis
drs. J. Endrullis
Hoorcollege, Werkcollege

Doel vak

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

The course is divided into the following parts: automata & languages and
computability theory (and, if time permits, quantum computing).

Inhoud vak

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.

If there is enough time left, 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.


4 hours per week lectures; 4 hours per week exercise classes


Weekly homework exercises (which can earn up to 0.5 bonus points). The
homework is mandatory to qualify for the exam.

Written exam.


Peter Linz, An Introduction to Formal Languages and Automata, Jones &
Bartlett, 4th or 5th edition



© Copyright Vrije Universiteit Amsterdam
asnDCcreatorasvVUAmsterdam asnDCdateasv2017 asnstudyguideasvmodule asnDCidentifierasv50052470 asnDCtitleasvAutomataandComplexity asnperiodasv140 asnperiodasv asncreditsasv6p0 asnvoertaalasvE asnfacultyasv50000044 asnDCcoverageasvdrsJEndrullis