Formal language theory

A.Y. 2020/2021
Overall hours
Learning objectives
The aim of the course is to present the foundations of formal languages and automata theory, together with some recent developments and relevant open problems.
Expected learning outcomes
The student should be able to use formal language and automata theory to formally describe the syntax of simple artificial languages (for instance programming languages) or of simple computational models. The student should be also able to compare different formal models with respect to the computational power and to the complexity of their descriptions.
Course syllabus and organization

Single session

Lesson period
Second semester
Course syllabus
The most important results on the classes of languages in the Chomsky hierarchy and on the corresponding computational models will be presented, by revising in a deeper and more detailed forms some of the topics of the undergraduate course on Formal Languages and Automata. A special emphasis will be on the computational resources which are required to recognize different classes of languages and, more in general, to descriptional complexity aspects.
Some of the lectures will be dedicated to the presentation of recent development of the research in the area and to open problems.

A detailed program, with the topics of each lecture, is published on the course webpage.
Prerequisites for admission
The knowledge of fundamental notions on finite state automata, regular languages and pushdowm automata is required. These notions are presented, for instance, in the Bachelor course of Automata and Formal Languages.
Teaching methods
Frontal lectures.
Teaching Resources
Course website:

J. Shallit, A Second Course in Formal Languages and Automata Theory. Cambridge University Press, 2009
J. Hopcroft and J. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979 - Notice that in that the next editions of the book (2000, 2006), which are more oriented to base courses, many of the topics have been removed or are presented in a less detailed way.
J. Hopcroft and J. Ullman, Formal languages and their relation to automata. Addison Wesley, 1969 - This is "precursor" of the book of 1979. It is well written, but it is not updated on some of the topics. The book is available of the ACM Digital Library (it can be freely download from computers connected to university network).
Assessment methods and Criteria
The exam consists of an oral discussion on the course topics.
The evaluation, expressed in thirtieths, is given by taking into account how much the student is able to master the course topics, the clarity of exposition and the language property.
INF/01 - INFORMATICS - University credits: 6
Lessons: 48 hours