Automata Theory

fall 2024

Toren Academiegebouw

Latest news

(13.12.2024) The recordings of all lectures from this year are available.

(13.12.2024) On Tuesday, 17 December, there will be a Q&A session for the exam. See below.

(13.12.2024) There is a list of exam topics available. See below.

(13.12.2024) For some parts of the material we have written lecture notes. See below.

(02.12.2024) The fourth homework assignment is available. See below.

(13.09.2024) The retake has moved from 20 January to 24 January, 2025. See below.


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: Mark van den Bergh
residing at: room Gorlaeus BM.2.01
email: m(dot)j(dot)h(dot)van(dot)den(dot)bergh(at)liacs(dot)leidenuniv(dot)nl
Lecturer 2: Rudy van Vliet
residing at: room Gorlaeus BM.2.03
telephone: 071-527 2876
email: rvvliet(at)liacs(dot)nl
Assistants for the exercise classes and the homework assignments: Dirck, Eef, Jip, Lucas, Perri, Simone, Thomas, Tiemen
General email address assistants: automata(at)liacs(dot)leidenuniv(dot)nl
Types of education: Every week a two-hour lecture and a two-hour exercise class. In addition, four homework assignments are provided.
Lectures: Mondays, 11:00-12:45, in room C3 of the Lecture Hall (the `dish'), by Mark van den Bergh (first half of semester) and Rudy van Vliet (second half of semester)
Exercise classes: Fridays, 11:00-12:45, in Gorlaeus BW.0.40 only (but always check MyTimeTable), by the assistants. All from 2 September to 13 December 2024. There is no lecture on 21 October (fall break) and there are no exercise classes on 4 October (Leidens Ontzet) and 25 October (fall break). On 22 November we use room BW.0.05 instead of BW.0.40 for the exercise class.

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. Last year's lectures (all of them!) can be viewed from this page.

Study load

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

Recommended prior knowledge

Foundations of Computer Science.

Contents

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 2024-2025 one is referred to the general webpage in the prospectus.

Learning objectives

After this course, students are able to

Examination

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.

Partial grades received in earlier years for homework and/or exam cannot be carried over to the new year.

Exams

There will be two exams (on campus):
First exam: Thursday, 19 December, 2024, 09:00 - 12:00, in Gorlaeus BM.1.26, BM.1.33, EM.1.09 and Lecture Hall C3
Retake: Friday, 24 January, 2025, 09:00 - 12:00, (new date!) in Universitair Sportcentrum
The grades will be published in Brightspace. Hence, make sure that you have registered for the course there.

Question-and-answer session

On Tuesday, 17 December, 2024, there is a question & answer session for the exam, in Gorlaeus BW.0.31 and BW.0.32. Then you can ask the questions that came up while studying for the exam. The session starts at 13.15, and lasts until 15.30 at the latest. If we run out of questions earlier, then the session also ends 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. We may even involve the board of examiners in such occasions.
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 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:

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.

Literature

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 be happy to add them to the list.

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

For some parts of the material (including the pumping lemma for regular languages), we have written lecture notes, based on the book and on the lectures.

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 three 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 14, on 13 December, 2024, hence complete!).

(A version of) The slides used during the lectures and exercise classes will be published below before every lecture and exercise class.

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 2023. You can find that edition's website 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: 13 December, 2024 - https://www.liacs.leidenuniv.nl/~vlietrvan1/automata/