(Ultimo aggiornamento: 25 Marzo 2007)
Docente: Alessandro Sperduti
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 di riferimento:
LUCIDI E NOTE DEL CORSO:
Lucidi della lezione del 27 Gennaio, 3 e 9 Febbraio
Lucidi aggiuntivi della lezione del 9 Febbraio