Automata Theory

fall 2023

Toren Academiegebouw

Latest news

The review session for the retake of 27 March will be on Tuesday, 21 May, 15.00-17.00, in Snellius 402.

The retake of 27 March, 2024, has been graded. Grades have been published in Brightspace. A review session for the exam has yet to be planned.

Automata Theory is a mandatory second year course in the bachelor Informatica and the bachelor Data Science and Artificial Intelligence at Universiteit Leiden.

Practical information

Lecturer 1: Dalia Papuc
residing at: room 131 of Snellius
email: d.papuc(at)liacs(dot)leidenuniv(dot)nl
Lecturer 2: Rudy van Vliet
residing at: room 140 of Snellius
telephone: 071-527 2876
email: rvvliet(at)liacs(dot)nl
General email address: automata(at)liacs(dot)leidenuniv(dot)nl
Assistants for the exercise classes and the homework assignments: ...
Types of education: Every week a two-hour lecture and a two-hour exercise class. In addition, four homework assignments are provided.
Lectures: Mondays, 17:15-19:00, in room C1 of the Lecture Hall (the `dish'), by Dalia Papuc (first half of semester) and Rudy van Vliet (second half of semester)
Exercise classes: Wednesdays, 09:00-10:45, in varying rooms of varying buildings (check MyTimeTable), by the assistants.
All from 4 September to 13 December 2023. There are no lectures on 2 October (Leidens Ontzet), 23 October (fall break) and no exercise classes on 25 October (fall break).

There will not be live streams of the lectures. The lectures will, however, be recorded. The recordings become available two weeks after every lecture, at this page.


This course is worth 6 EC. The level of the course is denoted as `200'.

Recommended prior knowledge

Foundations of Computer Science.


Automata theory and formal languages form the foundations of theoretical computer science, as they allow us to talk precisely about what an algorithm or a computation is, and what the complexity of an algorithm is. An automaton is in fact a model of computation that can be defined mathematically. Formal languages are used to describe the result of the computation, and the computational power of the model as such.

The simplest automaton that we will consider in this course is the finite automaton: a machine that is only able to keep track of its current state but has no memory. Finite automata specify an algorithmic procedure for recognizing whether a word is in a language. We will concentrate on the relationships between languages recognized by a finite automaton, languages generated by a grammar and languages described by a so-called regular expression. We will obtain algorithms for translating one description of a language into another.

Adding a restricted form of memory to finite automata increases its expressivity. We will study push-down automata, i.e. the class of automata with an auxiliary memory organized as a stack. The languages accepted by a push-down automaton can be generated by context-free grammars, which also play a crucial role in the definition of programming languages. Push-down automata, in turn, are important in compiler design and parsing.

Both for finite automata and push-down automata, we compare the deterministic and the non-deterministic variants. We also explore closure properties, which may be used to build more complex languages from simple languages. We finally study the limitations of both models with so-called pumping lemmas.

For global information about the course in studyyear 2023-2024 one is referred to the general webpage in the prospectus.

Learning objectives


Four homework assignments in the course of the semester, and a written exam at the end of the semester. The minimum grade for every homework assignment is 0, the minimum grade for the exam is 1. The homework assignments are not mandatory, but do count for the final grade. The grade for the exam must be at least 5.5. In that case, the final grade is a weighted average of the exam grade (70%) and the average homework grade (30%). If this weighted average happens to be less than 5.5, then the final grade will still be sufficient (6.0). If the exam grade is less than 5.5, then the final grade will be equal to the exam grade.


There will be two exams (on campus):
First exam: Thursday, 21 December, 2023, 09:00 - 12:00, in Universitair Sportcentrum.
Resit: Wednesday, 27 March, 2024, 13:30 - 16:00, in Gorlaeus Lecture Hall (the `dish'), C4/5.
Both exams can be found in the list of old exams at the bottom of this page. For the first exam, there is also a solution of the lecturers available.
Both exams have been graded. The grades, including final grades can be found in Brightspace.

Question & answer session

On Monday, 18 December, 2023, there is a question & answer session for the exam, in room Snellius 412. Then you can ask the questions that came up while studying for the exam. The session starts at 13:00 and lasts until 15:00 at the latest. If we run out of questions before 15:00, then we will stop earlier.

Homework assignments

In the course of the semester, four homework assignments will be launched. Together, they account for 30% of the final grade.
The homework assignments must be made individually. When we conclude that students have worked together too much for their solutions to a homework assignment, we will divide the points (for the solutions involved) by the number of students involved.
Solutions to homework assignments must be submitted on or before the deadline. Usually, this will be about two weeks after publication of the assignment. If you don't make it before that deadline, it is no use submitting your solution after all. That is, you will not earn points for it.
You are not obliged to make the homework assignments. However, it is wise to do so, because: (1) it is a useful exercise for the exam, and (2) if you miss one or more homework assignments, you will get a 0 for those assignments, and that may have a negative impact on your final grade for the course.

Results for the homework assignments of this course from an earlier year are no longer valid.

You can submit your solutions for the homework assignments via Brightspace. Make sure that you have been registered for the course there. The grades for the homework assignments will also be published in Brightspace.

Once the homework assignments are available, they will be published below. Currently, the following homework assignments are available:

All homework assignments have been graded. Feedback on the submissions has been sent to the students. The grades have been published in Brightspace.

If you wish to draw finite automata digitally, you may use the Finite State Machine Designer. Should the notation used in the tool deviate from the one we use in the course, please make this explicit when you submit your solution to the homework assignment.


John C. Martin, Introduction to Languages and the Theory of Computation, 4th edition, McGraw Hill, 2010/2011.

Two times the 4th edition: the American edition (ISBN-13: 978-0073191461) and the international edition (ISBN-13: 978-007-128942-9)
NB: this book is used also for the course Computability.
A list with errata to this book is available. If you find other errors in the book, please mention this to Rudy van Vliet. He would love to add them to the list.

This book is not in print anymore. You may find a second-hand copy online.

Exam topics

The topics for the exam consist of Altogether this has become: Even when proofs are no exam topics, the corresponding constructions are, unless explicitly stated otherwise.

N.B: The exam topics are not exactly the same as in earlier years. In particular, the following two topics do not have to be known for the exam this year:

N.B: Often, there exist several constructions to yield the same goal. The internet is full of it. For the homework assignments and the exam, it is important that you use the constructions as they have been treated in this course. Otherwise, points may be deducted.

Remarks: Concepts, notations and techniques covered in the course Foundations of Computer Science, in particular induction, are supposed to be known. You must be able to use them in the present course.

Treated material, exercises and slides

For those who have to miss a lecture or exercise class, we will maintain a list of the topics and exercises we have treated every week. You can find this overview here (updated till exercise class 13, on 13 December, 2023, so complete!)

The slides used during the lectures and exercise classes, will be published below before every lecture and exercise class. They will not be removed before the resit of the exam.

In the slides of the lectures, we regularly refer to two textbooks:
[M]: the book of John C. Martin mentioned above
[L]: Peter Linz: An Introduction to Formal Languages and Automata

Solutions to selected exercises

There are solutions available to a subset of the exercises from the book, some of which are also treated in the exercise class. You find these solutions below. At the end of the book, there is also a section containing solutions to a selection of the exercises.

Old exams:

The previous time the course was taught, was in fall 2022. You can find that edition's website (in Dutch) here. You can also find more old exams there.
Questions and remarks may be sent to:
Rudy van Vliet; rvvliet(at)liacs(dot)nl
Last modified: 21 May, 2024 -