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 The teaching presents concepts and results of Automata Theory and of Computability Theory of fundamental importance in the cultural background of a computer scientist. 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. AIMS AND LEARNING OUTCOMES At the end of the teaching the student/student will be able to: Know some fundamental concepts and results in the culture of acomputer science (abstract machine, language recognition, computable function, decidability, haltingproblem). Develop simple automata, including through the use of simulators. PREREQUISITES Basics of sets and functions Programming experience in some language. 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 Ricevimento: By appointment via email LESSONS LESSONS START According to the calendar approved by the Degree Program Board: https://corsi.unige.it/corsi/8759/studenti-orario Class schedule The timetable for this course is available here: Portale EasyAcademy EXAMS EXAM DESCRIPTION The examination consists of a written test and an oral test.In order to take the oral test,it is necessary to have passed the written test. ASSESSMENT METHODS The written test verifies the student's ability to put into practice the concepts seen in class. The oral test verifies the understanding of the concepts and the ability to illustrate them in appropriate way. FURTHER INFORMATION Contact the instructor for any additional information not included in the course description.
