Description
Selected topics (capita selecta) in formal languages, based on the book
Second Course in Formal Languages and Automata Theory by Jeffrey Shallit.
Contents
- Review of formal languages and automata theory;
- Combinatorics on words;
- Finite automata and regular languages;
- Context-free grammars and languages;
- Parsing and recognition;
- Turing machines;
- Other language classes.
Additional topics will be added at the whims of the lecturer and/or by request of the students, like
- Logic and automata;
- Automata on trees;
- Visibly pushdown automata.
Literature
Mandatory: Second Course in Formal Languages and Automata Theory by Jeffrey Shallit, Cambridge University Press, 2008, ISBN-13: 9780521865722.
Prerequisites
Basic knowledge in Automata and Formal Languages, e.g., as in the Leiden courses Fundamentele Informatica 2 and 3.
Examination
The course is fulfilled by solving a huge number of the exercises in the course book, and/or by writing short papers on its topics based on a literature study. No closing written examination.