Anno accademico 2020-2021


Agostino Dovier
Anno di corso: 2
Totale crediti: 9
Tipologia: Caratterizzante
Periodo didattico: Secondo Periodo
Prerequisiti. The student should have basic notions on (recursive) programming, discrete matyhematics, calculus and mathematical logics.
Metodi didattici. The material is classical and this applies to teaching methodology as well: lectures using blackboard and exercises.
Modalità di verifica. Written and oral examination. The written part is aimed at verifying the capability of applying the techniques the course deals with. During the oral examination the knowledge of the course program is verified.
Altre informazioni. Previous exams (most of them with solutions) are available from teacher personal web site.


We will consider the theoretical foundations of Computer Science.


1.1  Knowledge and understanding: the student will acquire the basic theoretical notions at the baseis of computer Science. In particular, she/he will know and understand the notions of formal language and its classification according to Chomsky, the notion of computable function and its main characterizations and limits, the notion of complexity of a problem and the main techniques for studying it.

 1.2 Applying knowledge and understanding: being capable of understanding the complexity of a formal language, the student will be able to choose the best software tool for generating or recognizing it. The student will be capable of understanding whether a problem can be solved by a computer or not, and, in the first case to understand if it can be solved efficiently or not.


2.1 Making judgements: given the formal specifics of a problem, the student will acquire the capability of deciding whether it can be solved or not by a computer and, in the first case, its degree of complexity.  

2.2 Communication: the student will learn the exact terminology of the foundations of computer science and therefore to use properly: notions of formal languages theory (automata, grammars, etc), of computability (decidable problem, semi decidable problem, productive, creative, simple sets, etc), and of complexity (polynomial problems, NP class, etc).

2.3 Lifelong learning skills: the student will learn how the scientific method can be applied to computer science. Moreover, being the main suggested textbooks in English, she/he will improve her/his language skills.


The course is organized in three parts: formal languages, computability, and complexity.

Formal languages.

Regular languages. Deterministic and non-deterministic finite state automata and their equivalence. Regular expressions.

The pumping lemma for regular languages and its applications.

Closure and decidability properties of regular languages.

Context-free languages. Context Free Grammars and derivation trees.

Ambiguous grammars and languages. Chomsky and Greibach normal forms.

The pumping lemma for context-free languages and its applications.

Closure and Decidability properties of context free languages.

Linear grammars, type 0 and type 1 grammars and Chomsky hierarchy.


Models for computation. Turing Machine. Turing-computability, enumeration,

Halting problem and Theorem SMN. (Primitive) recursive functions.

Equivalence theorem between the two formalisms.

Kleene recursion theorems, Rice and Rice-Shapiro theorems and their applications.

Reducibility between sets. Recursive and complete sets. The Myhill Theorem.

Simple Sets: definition, properties and their existence.


Languages and Problems. Deterministic and non-deterministic

time complexity classes; space classes: main results and relative relationships.

Reductions and Completeness. Cook’s Theorems.

NP-completeness of some fundamental problems using reductions.



Fondamenti dell’Informatica: Linguaggi Formali, Calcolabilità e Complessità.


ISBN 9788833933795