CODE 80303 ACADEMIC YEAR 2025/2026 CREDITS 6 cfu anno 3 INFORMATICA 8759 (L-31) - GENOVA SCIENTIFIC DISCIPLINARY SECTOR INF/01 LANGUAGE Italian TEACHING LOCATION GENOVA SEMESTER 2° Semester TEACHING MATERIALS AULAWEB OVERVIEW We introduce notions and results from Automata Theory and Computability Theory which are of paramount importance for a computer scientist. Since the course is given in Italian, please have a look at the italian version of this page for further information. AIMS AND CONTENT LEARNING OUTCOMES To understand key concepts of Theory of Automata and Theory of Computability, such as expressive power of automata, and decidability and semi-decidability of problems. TEACHING METHODS Traditional. SYLLABUS/CONTENT Automata and Languages Alphabets, strings, languages Deterministic (DFA) and non deterministic (NFA) finite state automata DFA minimization, regular expressions Closure properties of regular languages, pumping lemma Context-free grammars, deterministic and non deterministic push down automata (PDA) Closure properties of context-free languages, pumping lemma Computability Turing machines, accepted languages Indecidability, recursive and recursively enumerable languages, universal language and machine, indecidability of the universal language Halting problem Indecidable problems on Turing machines, Rice theorem, Church thesis RECOMMENDED READING/BIBLIOGRAPHY Course notes. TEACHERS AND EXAM BOARD ARNAUD HENRI PAUL SANGNIER Ricevimento: Reception through appointment via mail. FRANCESCO DAGNINO LESSONS Class schedule The timetable for this course is available here: Portale EasyAcademy