There are now videos of the material you must refresh before the course
here.
Lecture notes
- The lecture notes can be
found here. Note
that some pages use color!
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.
Added on October 23, 2020: 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 in later chapters the solutions are often
only sketched and have not been yet revised.
Please be aware that these solutions are bound to contain typos,
notation inconsistencies, and minor mistakes. I will be grateful for any pointers to mistakes, but I
may not have time to correct them before the end of the course.
The version with solutions has replaced the previous one at the link above.
- Here you can find an online
collection of examples. It is seriously outdated, it was written
for an old version of the lecture notes.
Literature
- 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).
- Debasis
Mitra's slides
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
Computation;
McGraw-Hill, 2002.
- Michael Sipser;
Introduction to the Theory of
Computation;
Course Technology, 2005.
- Joerg Flum, Erich Graedel, Thomas Wilke (eds.);
Logic and
Automata: History and Perspectives, Volume 2;
Amsterdam
University Press, 2008.
- Dominique Perrin, Jean-Eric Pin;
Infinite Words: Automata,
Semigroups, Logic and Games;
Academic Press, 2004.
Slides
- Introduction
- Automata as data
structures
- Automata
classes and conversions
- Minimization
- Implementing
operations on sets
- Implementing
operations on relations
- Pattern matching
- Fixed-length
languages
- Verification
- Monadic second-order logic on
words
- Presburger Arithmetic
- Omega-automata
- Implementing boolean operations
- Emptiness checking
- Verification of liveness
properties
Tools
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
connection.
-
JFLAP Game. A game for practicing automata, regular
expression and temporal logic interconvertions.
- Owl. A Java tool collection and library for Omega-words, ω-automata and Linear Temporal Logic (LTL). Batteries included.
- Automata Tutor. An
online tool in which to practice exercises with automata and get feedback.
- SPOT. An
online tool for ω-automata and Linear Temporal Logic (LTL).