Course presentation form (available also as a pdf file)
Objectives. The main objective of the Formal Languages course is to introduce the fundamental notions about formal languages and the mechanisms for representing them. The course will focus on the formal languages that find most applications in computer science, namely regular and context-free languages. Students should become familiar with the fundamental representation mechanism for such languages, which span machine-based models (finite state machines for regular languages), algebraic models (regular expressions), and generation-based models (formal grammars). The aim is to exploit such representation mechanisms to study the properties of the different types of formal languages and the main algorithms for processing languages, which help to solve problems that are of practical relevance. A second objective of the course is to get students acquainted to a formal, rigorous approach in computer science.
Prerequisites. There are no prerequisites in terms of courses to attend. Students should be familiar with notions of mathematics and set theory, as taught in the mathematics courses of the first year.
[M1] Introduction to Automata Theory, Languages, and Computation (3rd edition). J.E. Hopcroft, R. Motwani, J.D. Ullman. Addison Wesley, 2007.Further reading material for interested students
[M2] Lecture Notes for Formal Languages. Diego Calvanese. 2009. Available on the course web page as scanned pages in pdf.
See also RIS
calendar for changes.