Automata and Formal Languages 2017/18
- The lecture notes can be
found here (Oct. 10, 2017). The
updated lecture notes can be
found here (Feb. 6, 2018). Note
that some pages use color! Printed copies can be obtained from the
Fachschaft at a very low price, if some student volunteers to
organize the process.
The lecture notes have already been revised several times, but they
may still contain typos or mistakes. Please email me if you find
some. If there is some important error then I will call your attention
to it through the News.
- Here you can find an online
collection of examples. It is seriously outdated, it was written
for an old version of the script.
- My slides for the course Introduction
to Theoretical Computer Science (in German), with the material on
Automata Theory of which we assume knowledge (NFAs, DFAs, regular
expressions, conversion algorithms, closure under boolean operations,
pumping lemma, minimal DFAs).
from his introductory lecture (in English). Remark: this is just
one of the many sets of slides available on line.
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman;
Introduction to Automata Theory, Languages and Computation;
Addison-Wesley Longman, 3rd edition, 2006.
- John Martin;
Introduction to Languages and the Theory of
- Michael Sipser;
Introduction to the Theory of
Course Technology, 2005.
- Joerg Flum, Erich Graedel, Thomas Wilke (eds.);
Automata: History and Perspectives, Volume 2;
University Press, 2008.
- Dominique Perrin, Jean-Eric Pin;
Infinite Words: Automata,
Semigroups, Logic and Games;
Academic Press, 2004.
Here are the slides. During the course in WS16/17 I have corrected
some typos, and rewritten the last two sets of slides (emptiness
checking and verifcaition of liveness properties). If you only
downloaded the slides at the beginning of the course, it is advisable
to download them again.
- Automata as data
classes and conversions
operations on sets
- Pattern matching
operations on relations
- Monadic Second-order Logic on
- Implementing boolean operations
- Emptiness checking
- Verification of liveness
properties: old slides, updated slides
In both exercises and class we will demonstrate and use a number of
tools to illustrate the theory and to present typical
applications. They may include:
- JFLAP. Automata
on finite words
- SPIN. Verification
using automata on infinite words
- MONA. Logic and automata
- LTL2BA. Automata
and temporal logic.
- GOAL. Büchi
Automata and temporal logic, interactive graphical tool
JFLAP Game. A game for practicing automata, regular
expression and temporal logic interconvertions.