Automi e Linguaggi formali - A.A. 2014/2015
Aggiornato il 22/12/2014
ATTENZIONE: gli esiti del I Compitino sono stati pubblicati su UniWeb La sessione di correzione/visione compitini si svolgera' Mercoledi' 7 Gen 2015 alle ore 13:30 in Aula LUM 250
Programma
Questo corso fornisce i concetti fondamentali della teoria degli automi e dei linguaggi formali, mostrando la loro applicazione ai compilatori. Va anche in dettaglio nelle due fasi di analisi lessicale e sintattica dei compilatori. Inoltre, introduce le nozioni di indecidibilita' e intrattabilita'. Gli argomenti principali del corso sono: analisi lessicale, automi a stati finiti, espressioni e linguaggi regolari, analisi sintattica, grammatiche e linguaggi liberi dal contesto, automi a pila, macchine di Turing, concetto di indecidibilita', problemi intrattabili, classi P e NP.
Orario lezioni (Aula: LUM 250)
Lunedi', Martedi' 15:30-17:30 Mercoledi' 13:30-15:30
Prova parziale
Martedi' 18 Nov 14:30 (Aula: LUM 250)
Esercizi di preparazione (Aula: LUM 250)
Mercoledi' 12 Nov 13:30-15:30
Ricevimento
Martedi' ore 10:30 - 12:30 Giovedi' per appuntamento
Lucidi lezioni
-
"Introduzione al corso"
[.pdf ] -
"Struttura di un compilatore e fasi principali"
[.pdf - handouts ] -
"Introduzione a linguaggi regolari ed automi a stati finiti"
[.pdf - handouts ] -
"Introduzione alle dimostrazioni formali"
[.pdf - handouts ] -
"Linguaggi regolari ed automi a stati finiti"
[.pdf - handouts ] -
"Espressioni regolari"
[.pdf - handouts ] -
"Proprieta' dei linguaggi regolari - Pumping lemma"
[.pdf - handouts ] -
"Proprieta' dei linguaggi regolari (cont)"
[.pdf - handouts ] -
"Proprieta' dei linguaggi regolari - Minimizzazione"
[.pdf - handouts ] -
"Grammatiche libere da contesto"
[.pdf - handouts ] -
"Grammatiche libere da contesto - Alberi sintattici"
[.pdf - handouts ] -
"Grammatiche libere da contesto - Ambiguita'"
[.pdf - handouts ] -
"Pushdown automata"
[.pdf - handouts ] -
"Proprieta' dei linguaggi liberi da contesto"
[.pdf - handouts ]
Sito principale per il corso (Prof. Sperduti) [link]
Corso e lucidi anni precedenti (Prof. Rossi) [link]
Homework