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.
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.
TESTI DI RIFERIMENTO
Fondamenti dell’Informatica: Linguaggi Formali, Calcolabilità e Complessità.
BOLLATI BORINGHIERI, 320 pagine, MARZO 2020.