Select Academic Year:     2016/2017 2017/2018 2018/2019 2019/2020 2020/2021 2021/2022
First Semester 
Teaching style
Lingua Insegnamento

Informazioni aggiuntive

Course Curriculum CFU Length(h)
[60/61]  COMPUTER SCIENCE [61/00 - Ord. 2016]  PERCORSO COMUNE 6 48


1. Knowledge and comprehension skills.
The course will expose students to the theory of automata and formal languages. In particular, the student will learn some basic techniques on the formal modelling and analysis of software systems, and on the limitations of computing machines. The various topics presented in the course will be supported by formal arguments, allowing students understand the proof of simple properties of formal systems.

2. Ability to apply knowledge and comprehension.
Students will learn some basic skills in the abstraction of practical problems through formal models, and in particular how to
apply simple algorithms on formal languages, and to use some software tools based on the theory of automata.

3. Making judgments.
The course provides students with the basic skills to apply the techniques described during the course to the solution of technical problems related to the topic of the course.

4. Communication skills.
The lectures will include frequent interactions with students, who will learn how to properly communicate the studied topics.

5. Learning skills.
The course provides students with sufficient skills to understand advanced textbooks on the course topic, allowing them to autonomously expand their knowledge.


Some basic knowledge of discrete math, set theory, mathematical logic and proof techniques, algorithms and data structures is useful.


- Logical notation
- Sets, functions and bijections
- Recursive definitions and inference rules
- Languages
- Proof procedures for propositional logic
- Functional programming in Ocaml
- Labelled transition systems
- Finite state automata
- From non-deterministic to deterministic FSAs
- Pumping lemma for regular languages
- Decision procedures for regular languages
- Turing machines
- Non computable functions
- Computational complexity

Teaching Methods

The course consists of 24 classes, of 2 hours each (48 lecturing hours in total). These lectures also include exercises, where students are required to apply the studies techniques. A tutoring course will run in parallel with the main course, to help students in the preparation of the final exam. The lecturer will support students throughout the whole academic year, either through office hours and the elearning site of the course.

Classes will be given in hybrid form, so to make them available both to students attending in the classroom, and to students connected from home. At the beginning of the semester, each student must choose for the "classroom option" or the "online option". Depending on the actual number of seats in the classroom, students who have chosen the "classroom option" could be admitted to the totality or to a part of the classroom lectures.

Verification of learning

The exam consists of a written and an oral part, crafted to verify the knowledge and skills acquired by students.

Depending on the situation with the COVID-19 emergency, the test could be performed through on online platform.


Reference text: lecturer's notes (in english)

Other suggested texts:

Hopcroft, Motwani, Ullman. Automi, linguaggi e calcolabilita'. Pearson, 2009.

Functional programming in Ocaml: https://www.cs.cornell.edu/courses/cs3110/2019sp/textbook/

More Information


Questionnaire and social

Share on: