There was a typo in the set of slides about verification of liveness properties, namely, the definition of the Until operator (slide: Semantics of LTL).
We have corrected it: 0 \le i \le k (wrong) is now replaced by 0 \le i < k (correct).
An inconsistency between the slides for Implementing Boolean Operations and the lecture notes
has been corrected. It concerns the definition of the initial states of the complement automaton,
which was done in slightly different ways (both correct).
The new version of the set of slides for Implementing Boolean Operations, and the new
version of the lecture notes (with changes in Chapter 12), can now be downloaded
from the web page of the course.
There is a typo in the algorithm NCAtoDCA in page 242 of the lecture notes. In line 5,
if P=\emptyset then ...
it should be
if O=\emptyset then ...
Due to confusion in the dates, the lecture started (very) late today. If you left before it started,
you can rewatch it
(the empty beginning has been edited out). We are sorry!
In view of the current health situation, we have decided to switch our tutorials to an all-online format.
We tried an in-person tutorial yesterday: the contact-tracing QR codes did not work for everyone, the room
was hard to ventilate properly, and some students expressed their concerns. Once the lockdown period is over,
we will re-evaluate this decision and consider going back to in-person tutorials. We are sorry to make this
sudden change, we hope you understand. We must all be flexible in dealing with the ever-changing restrictions.
Instead of the current in-person tutorials, starting next week (10.11.2020) we will conduct the tutorial
sessions on BBB at this link (no sign up
or app needed) at the same time as before, 10:00 - 11:30 on Tuesdays. To make it interactive, we will use the
whiteboard and shared notes functions of BBB. We encourage you to use these as well as your microphone so that
we can recreate the tutorial setting as much as possible.
If you have comments, feel free to use the
general forum on the
In view of the current situation we have decided that you should FOLLOW THE LECTURES THROUGH THE LIVESTREAM,
and not come to the lecture in person until further notice. The TUTORIALS WILL STILL HAPPEN IN PERSON though!
There are now videos of the material you must refresh before the course
The lectures will be livestreamed here
and the videos will then be available to (re)watch.
IMPORTANT: Due to the pandemic, this term it is particularly important that you have material to work from
home. For this reason I have decided to put online a version of the lecture notes containing
solutions to the exercises, even though the solutions in the later chapters are often
only sketched and have not been yet revised. Please be aware that these solutions are bound to contain contain typos,
notation inconsistencies, and minor mistakes. The version can be found under "Material", and replaces the old version.
This year's winter term is shorter than usual, and so the structure of the course is going to change a bit.
Usually, the first three weeks are devoted to refreshing and deepening contents that you already learned
in your Bachelor course on Automata Theory. (For TUM students this course is the first half of IN0011 "Introduction to
Theoretical Computer Science", also known as THEO; for other students if could be a course on Formal Languages and Automta,
or even a course on Compilers.) This year we (a) leave most of the "deepening" out, and (b) request that you refresh
some material on your own.
The material you're expected to refresh is:
The lecture notes are available through the Menu point "Material".
- Automata Classes and Conversions: (Chapter 2 of the lecture notes)
- DFA Minimization (Sections 3.1, 3.2 (without section 3.2.3) and 3.4 of Chapter 3 of the lecture notes)
During the first week of the course we will also quickly revise these topics, but in the
second week we will already start with Chapter 4.
The first two tutorials (on November 3 and November 10) will be on automata classes, conversions, and minimization.
Under "Exercises" you can also find exercise sheets of past years (typically the first three sheets).
You can now find the description of the tutorial formats here.
The lecture room has been changed. Both lectures and tutorials will be held in Hörsaal 2, "Interims I" (5620.01.102).
Both lectures and tutorials will be held physically. We are waiting for the official confirmation, but we also expect that the exam will be held in-person.
Creation of the site.