| CODE | 80303 |
|---|---|
| ACADEMIC YEAR | 2022/2023 |
| CREDITS |
|
| SCIENTIFIC DISCIPLINARY SECTOR | INF/01 |
| LANGUAGE | Italian |
| TEACHING LOCATION |
|
| SEMESTER | 1° Semester |
| TEACHING MATERIALS | AULAWEB |
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.
Office hours: 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)
All class schedules are posted on the EasyAcademy portal.
| Date | Time | Location | Type | Notes |
|---|---|---|---|---|
| 13/01/2023 | 09:00 | GENOVA | Scritto | |
| 03/02/2023 | 09:00 | GENOVA | Scritto | |
| 14/06/2023 | 09:00 | GENOVA | Scritto | |
| 27/07/2023 | 09:00 | GENOVA | Scritto | |
| 12/09/2023 | 09:00 | GENOVA | Scritto |