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.
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.
Traditional.
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
Course notes.
Ricevimento: On request. In addition, on aulaweb there will be a discussion forum for questions and answer of general interest for all students.
ELENA ZUCCA SCHILLANI (President)
DAVIDE ANCONA
FRANCESCO DAGNINO (President Substitute)
GIORGIO DELZANNO (Substitute)
