Automi e Linguaggi Formali
Contenuto e Struttura del
corso
aa 2014/2015
(Ultimo aggiornamento: 27 Dicembre 2014):
Regole appelli e voto complessivo:
- L'esame e' superato con i compitini se si e' ottenuto un voto di almeno 18 in ognuno dei compitini.
- Ad ogni appello, e' possibile sostenere l'intero esame. Chi ha ottenuto un voto di almeno 18 nel primo compitino, puo' sostenere solo la seconda parte.
Chi ha ottenuto un voto di almeno 18 nel secondo compitino, puo' sostenere solo la prima parte.
- Un voto di almeno 18 gia' ottenuto viene perso appena si consegna
un esame ad un successivo appello.
Docenti: Enrico Mezzetti, Alessandro Sperduti
Note introduttive
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.
Libri di riferimento:
-
Automi, Linguaggi e calcolabilita',
J. E. Hopcroft, R. Motwani, J. D. Ullman,
terza edizione, Pearson/Addison-Wesley, 2009.
-
Compilatori: principi, tecniche e strumenti (cap. 1,3,4),
A. V. Aho, M. S. Lam, R. Sethi, J. D. Ullman,
seconda edizione, Pearson/Addison-Welsley, 2009.
Calendario delle lezioni
Questa parte del corso si tiene con il seguente calendario: Lunedi e Martedi dalle 15:30 alle 17:30,
Mercoledi dalle 13:30-15:30 in aula
LuM250
(Paolotti) nel periodo 1 Ottobre - 24 Gennaio
2015
Ricevimento studenti prof. Sperduti
Il ricevimento studenti si svolge, tranne diverso avviso, con
il seguente calendario:
-
Venerdi 11:00 - 13:00 in stanza 403, Torre Archimede
-
se necessario, in aula LuM250 in date concordate
Modalita' d'esame:
- scritto ed eventuale orale se richiesto dal docente
- due compitini per prima e seconda parte del programma (se superato un compitino, all'appello si deve solo sostenere l'alra parte; se superati entrambi,
non e' necessario sostenere lo scritto agli appelli)
LUCIDI E NOTE DEL CORSO:
Lucidi per la prima parte dell'insegnamento (Enrico Mezzetti)
Analisi
sintattica (parte prima) 10, 11 Novembre
Parsing
Bottom-up 24 Novembre (file aggiornato: rimossi refusi)
Parsing
Bottom-up (seconda parte) 25, 26 Novembre (file aggiornato: rimossi refusi)
Parsing
Bottom-up (esempio esteso con derivazioni) 26 Novembre
Homework
S1
Parsing
Bottom-up (terza parte) 1, 2, 3 Dicembre (aggiornato alla lezione
del 3 Dicembre)
Homework
S2
Macchine
di Turing(prima parte) 15 Dicembre (inserito file con correzioni)
Macchine
di Turing(seconda parte) 16 Dicembre
Visione primo compitino: lezione del 7 Gennaio 2015.