Automata and Complexity

2019-2020
Dit vak wordt in het Engels aangeboden. Omschrijvingen kunnen daardoor mogelijk alleen in het Engels worden weergegeven.

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 require?".

The course is divided into the following parts: automata & languages and
computability theory.

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.

Onderwijsvorm

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

Toetsvorm

The homework is mandatory for qualifying for the exam (70% of the
homework points to qualify for the exam). In case at least 90% of the
homework points is obtained, 0.5 bonus point is awarded for the final
grade.
At the end of the course there is a final exam. The overall grade is the
grade of the final exam plus the possibly 0.5 bonus point obtained for
the homework. (The bonus is only added for students that pass the exam
with a grade of at least 5.5.)

There is no resit opportunity for the homework.

Literatuur

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

Doelgroep

3CS

Algemene informatie

Vakcode X_401049
Studiepunten 6 EC
Periode P4
Vakniveau 300
Onderwijstaal Engels
Faculteit Faculteit der Bètawetenschappen
Vakcoördinator drs. J. Endrullis
Examinator drs. J. Endrullis
Docenten drs. J. Endrullis

Praktische informatie

Voor dit vak moet je zelf intekenen.

Voor dit vak kun je last-minute intekenen.

Werkvormen Werkcollege, Hoorcollege
Doelgroepen

Dit vak is ook toegankelijk als: