PRESENTAZIONE

Il corso presenta concetti e risultati della Teoria degli Automi e dei Linguaggi e della Teoria della Calcolabilità di importanza fondamentale nel bagaglio culturale di un informatico.

OBIETTIVI E CONTENUTI

OBIETTIVI FORMATIVI

Introduzione a linguaggi formali e alla teoria degli automi e calcolabilità background considerato core tier nel curriculum ACM/IEEE 2013 e utile in vari contesti quali: compilatori, intelligenza artificiale, database, linguaggi per il web e metodi formali per l'analisi di sistemi

MODALITA' DIDATTICHE

Tradizionale

PROGRAMMA/CONTENUTO

Automi e Linguaggi
Alfabeti, stringhe, linguaggi
Automi a stati finiti deterministici (DFA) e  non deterministici (NFA)
Minimizzazione di DFA, espressioni regolari
Proprietà di chiusura dei linguaggi regolari, pumping lemma
Grammatiche context-free, alberi di derivazione, ambiguità
Automi push-down deterministici e non deterministici
Equivalenza di PDA e grammatiche CF
Proprietà di chiusura dei linguaggi CF, pumping lemma
 

Calcolabilità
Macchine di Turing (MdT), linguaggi accettati da MdT
Macchine di Turing non deterministiche
Nastri semi-infiniti
Altri tipi di macchine: multi-stack, counter machine
Indecidibilità, linguaggi ricorsivi e ricorsivamente enumerabili (RE), RE non ricorsivi, linguaggio e macchina universale, indecidibilità del linguaggio universale
Halting problem
Problemi indecidibili su MdT, teorema di Rice, tesi di Church

TESTI/BIBLIOGRAFIA

Note a cura del docente
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman Automi, linguaggi e calcolabilità.

DOCENTI E COMMISSIONI

Commissione d'esame

ELENA ZUCCA (Presidente)

DAVIDE ANCONA

GIORGIO DELZANNO

EUGENIO MOGGI

LEZIONI

Orari delle lezioni

FONDAMENTI DELL'INFORMATICA

ESAMI

MODALITA' D'ESAME

Scritto

MODALITA' DI ACCERTAMENTO

La prova scritta verifica la capacità dello studente di mettere in pratica le nozioni viste a lezione. La prova orale verifica la comprensione dei concetti e la capacità di illustrarli in modo appropriato.

Calendario appelli