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.
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
Tradizionale
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
Note a cura del docente John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman Automi, linguaggi e calcolabilità.
Ricevimento: Su appuntamento. Inoltre su Aulaweb è disponibile un forum per domande e risposte di interesse generale.
ELENA ZUCCA (Presidente)
DAVIDE ANCONA
GIORGIO DELZANNO
EUGENIO MOGGI
FONDAMENTI DELL'INFORMATICA
Scritto
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.
