(11.02.2025)
The retake exam of 24 January 2025 has in principle been graded.
We plan to perform a second correction on 14 February, so in the best
case, grades will be published at the end of that day.
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'.
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
design a finite automaton for a given language and interpret
finite automata
design regular expressions for a given language and interpret
regular expressions
design context-free grammars for a given language and interpret
context-free grammars
design pushdown automata for a given language and interpret
pushdown automata
reproduce and apply definitions of, e.g., the above concepts,
distinguishability, a derivation (tree), a computation
describe and apply constructions, e.g.,
to minimize finite automata
between finite automata and regular expressions
between finite automata and regular grammars
to convert context-free grammars into some normal form
between context-free grammars and push-down automata
prove and apply simple properties, including closure properties
and pumping lemmas
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 and C4/5.
This exam has been graded.
The exam grades can be found in
Brightspace.
Final grades in case of a sufficient exam grade will be calculated once
homework 4 has been graded.
Retake:
Friday, 24 January, 2025, 09:00 - 12:00,
(new date!)
in Universitair Sportcentrum
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.
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:
homework 1
Submission deadline:
Monday 7 October 2024, 11:00.
homework 2
Submission deadline:
Friday 1 November 2024, 23:59.
homework 3
Submission deadline:
Wednesday 27 November 2024, 23:59.
homework 4
Submission deadline:
Monday 16 December 2024, 23:59.
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
the topics presented and discussed at the lectures
with the corresponding exercises.
Altogether this has become:
Section 1.4
Chapter 2, minus
the proof of Theorem 2.36 `from right to left'
(that M_L indeed accepts L and is minimal)
Chapter 3, minus
construction and proof Theorem 3.17
inductive proof of correctness Theorem 3.18 (the construction itself
has to be known)
inductive proof for L(M1)* in Theorem 3.25
Section 3.5
but plus
alternative, simpler construction for Theorem 3.17 (without proof)
algorithm of Brzozowski and McCluskey (from lecture and Exercise 3.54)
Chapter 4, minus
pages 147-148
but plus
live, reachable, useful variables (from lecture and Exercises 4.51-4.53)
operations on languages (even/odd/chop) from lecture 11
(but not: attribute grammars)
Chapter 5, minus
inductive proof in both directions for Theorem 5.18
inductive proof in both directions for Theorem 5.23
inductive proof in both directions for Theorem 5.29
Section 5.5
Chapter 6, minus
second half of page 211 and pages 212-213
inductive proof of Theorem 6.13
Section 6.3
(Extra) closure properties of
regular languages (exercise class 6-7)
(deterministic) context-free languages (lectures 11, 14)
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:
algorithm of McNaughton and Yamada (from Section 3.5),
see slides of lecture 6
pre(L) for (D)CFL (from Exercises 5.20 and 6.22),
see slides of lecture 10
decision problems involving context-free languages (from Section 6.3)
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
Monday, 2 December, 2024,
slides lecture 13
acceptance by empty stack,
from pushdown automata to context-free grammars,
pumping lemma for context-free languages
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.
Solutions to exercises from
Chapter 1
(updated, 4 September, 2024)
Solutions to exercises from
Chapter 2
(updated, 19 November, 2024)
Solutions to exercises from
Chapter 3
(updated, 13 December, 2024)
Solutions to exercises from
Chapter 4
(updated, 18 November, 2024)
Solutions to exercises from
Chapter 5
(updated, 2 December, 2024)
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: 11 February, 2025
- https://www.liacs.leidenuniv.nl/~vlietrvan1/automata/
