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.
Studielast
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 2023-2024
one is referred to the
general webpage in the prospectus.
Learning objectives
Getting familiar with the theory of computation in general, and formal
languages, automata and grammars in particular.
Being able to construct automata, regular expressions and context-free
grammars to describe given languages.
Understanding the power and limitations of the models, and the relations between them.
Being able to prove simple properties and to apply 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.
Exams
There will be two exams (on campus): First exam:
Thursday, 21 December, 2023, 09:00 - 12:00,
in Universitair Sportcentrum.
This exam has been graded.
The grades, including final grades have been published in
Brightspace.
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.
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:
homework 1
Submission deadline:
Monday 9 October 2023, 23:59.
homework 2
Submission deadline:
Monday 6 November 2023, 23:59.
homework 3
Submission deadline:
Wednesday 29 November 2023, 23:59.
homework 4
Submission deadline:
Tuesday 19 December 2023, 23:59.
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.
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 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
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 variabelen (from lecture and Exercises 4.51-4.53)
operations on languages (even/odd/chop) from lecture 10
(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
(Extra) closure properties of
regular languages (exercise class 6)
(deterministic) context-free languages (lectures 9, 13)
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:
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
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
Monday, 4 September, 2023,
slides lecture 1
practical information, languages, finite automata
(note that these slides are not visible in the recording of the lecture)
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.
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: 1 April, 2024
- https://www.liacs.leidenuniv.nl/~vlietrvan1/automata/
