Corso di Automi e Linguaggi Formali

Docente: Francesca Rossi

Anno accademico 2005-2006

Voti compitini e primi tre appelli
Voti appello 13.9.2006

Programma:
Questo corso fornisce i concetti fondamentali della teoria degli automi e dei linguaggi formali, mostrando la loro applicazione ai compilatori. Inoltre, introduce le nozioni di indecidibilita' e intrattabilita'. Gli argomenti principali del corso sono: automi a stati finiti, espressioni e linguaggi regolari, grammatiche e linguaggi liberi dal contesto, automi a pila, macchine di Turing, concetto di indecidibilita', problemi intrattabili, classi P e NP, relazione con i compilatori.


Testo consigliato:

Orario: Lunedi' 15:30-17:30, Venerdi' 13:30-16:30, aula LUM250.

Cambiamenti di orario: Non si fara' lezione Venerdi' 27 Gennaio.

Orario di ricevimento: Giovedi' 16:00-18:00, studio


Modalita' d'esame: scritto ed eventuale orale se richiesto dal docente.

Compitini (se superati, sostituiscono lo scritto):

Appelli d'esame: due a fine corso (tra 21 Marzo e 16 Aprile), piu' due di recupero tra Luglio e Settembre


Lucidi del corso: Nota: i lucidi dei capitoli 1-7 sono basati su una traduzione dai lucidi in inglese di Gosta Grahne.


Francesca Rossi ( frossi@math.unipd.it)