CODE 80303 ACADEMIC YEAR 2019/2020 CREDITS 6 cfu anno 3 INFORMATICA 8759 (L-31) - GENOVA SCIENTIFIC DISCIPLINARY SECTOR INF/01 LANGUAGE Italian TEACHING LOCATION GENOVA SEMESTER 1° 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. 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, derivation trees, ambiguity 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 ELENA ZUCCA Ricevimento: On request. In addition, on aulaweb there will be a discussion forum for questions and answer of general interest for all students. Exam Board ELENA ZUCCA (President) DAVIDE ANCONA FRANCESCO DAGNINO GIORGIO DELZANNO EUGENIO MOGGI LESSONS Class schedule AUTOMATA THEORY AND COMPUTABILITY EXAMS Exam schedule Data appello Orario Luogo Degree type Note 22/01/2020 09:00 GENOVA Scritto 10/02/2020 09:00 GENOVA Scritto 16/06/2020 09:00 GENOVA Scritto 09/07/2020 09:00 GENOVA Scritto 14/09/2020 09:00 GENOVA Scritto
