We introduce notions and results from Automata Theory and Computability Theory which are of paramount importance for a computer scientist.
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 (President)
DAVIDE ANCONA
RICCARDO BIANCHINI (Substitute)
FRANCESCO DAGNINO (Substitute)
GIORGIO DELZANNO (Substitute)
