Formal Language Theory
A.Y. 2024/2025
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.
Lesson period: Second semester
Single course
This course cannot be attended as a single course. Please check our list of single courses to find the ones available for enrolment.
Course syllabus and organization
Single session
Responsible
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.
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 pushdown automata is required. These notions are presented, for instance, in the Bachelor course of Automata and Formal Languages.
Teaching methods
Frontal lectures.
Teaching Resources
References:
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).
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.
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
Professor:
Pighizzini Giovanni
Shifts:
Turno
Professor:
Pighizzini GiovanniProfessor(s)