Automata and Formal Languages

Automaten en Formele Talen

Course manual 2025/2026

Course content

Automata theory offers a framework to understand and define what machines can - and even more importantly - cannot do. The subjects of this course are:

Finite Automata

Regular Languages

PushDown Automata

Context-Free Languages

Turing Machines and Computability.

The course therefore has strong relations to Algorithms and Complexity, and introduces a crucial part of the foundations of Theoretical Computer Science.

Study materials

Literature

• Dexter C. Kozen, 'Automata and Computability', Springer, 1997.

Objectives

• The student can explore the possibilities and limitations of simple computational processes using formal methods.
• The student is able to explain the various topics in the course (finite automata and regular languages, push-down automata and context-free languages, and Turing machines).
• The student can apply the constructions and models covered in the course to solve simple problems.
• The student can categorize simple problems using concepts from the course.

Teaching methods

• Lecture
• Self-study
• Programming Exercises (with potential Check-Up session)
• Exercise Sessions (collaborative)

Afwisselend hoor- en werkcolleges. Aanwezigheid bij de hoor- en werkcolleges wordt sterk aanbevolen maar is niet verplicht.

Learning activities

Attendance

Assessment

Deadlines for assignments are dead-lines. If not submitted in time, an assignment will receive a score of 0 points.

The exam has a resit, but the exercise assignments do not. 

Assignments

There are three programming exercises (Python) to submit online, which are to be worked on individually.

The students will be graded and receive feedback via Canvas and the grading environment. 

Fraud and plagiarism

Over het algemeen geldt dat elke uitwerking die je inlevert ter verkrijging van een beoordeling voor een vak je eigen werk moet zijn, tenzij samenwerken expliciet door de docent is toegestaan. Het inzien of kopiëren van andermans werk (zelfs als je dat hebt gevonden bij de printer, in een openstaande directory of op een onbeheerde computer) of materiaal overnemen uit een boek, tijdschrift, website, code repository of een andere bron - ook al is het gedeeltelijk - en inleveren alsof het je eigen werk is, is plagiaat.

We juichen toe dat je het cursusmateriaal en de opdrachten met medestudenten bespreekt om het beter te begrijpen. Je mag bronnen op het web raadplegen om meer te weten te komen over het onderwerp en om technische problemen op te lossen, maar niet voor regelrechte antwoorden op opgaven. Als in een uitwerking gebruik is gemaakt van externe bronnen zonder dat een bronvermelding is vermeld (bijvoorbeeld in de rapportage of in commentaar in de code), dan kan dat worden beschouwd als plagiaat.

Deze regels zijn er om alle studenten een eerlijke en optimale leeromgeving aan te kunnen bieden. De verleiding kan groot zijn om te plagiëren als de deadline voor een opdracht nadert, maar doe het niet. Elke vorm van plagiaat wordt bestraft. Als een student ernstige fraude heeft gepleegd, kan dat leiden tot het uitschrijven uit de Universiteit. Zie voor meer informatie over het fraude- en plagiaatreglement van de Universiteit van Amsterdam: www.student.uva.nl

Course structure

Contact information

Coordinator

• dr. rer. nat. R.E.M. Reiffenhäuser

Staff