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.

• Automi, Linguaggi e calcolabilita' J. E. Hopcroft, R. Motwani, J. D. Ullman, Addison Wesley, 2003.

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):

• Primo compitino: Lunedi' 20 Febbraio ore 15:30 aule LUM250+LUF1+LUF2
• Secondo compitino: Venerdi' 17 Marzo ore 13:30 aule LUM250+LUF2.

• Primo appello:
  • scritto: 27 Marzo ore 10:00 in LUM250+P200
  • orale: 31 Marzo ore 10:00 in P200
• Secondo appello:
  • scritto: 3 Aprile ore 15:00 in P200
  • orale: 6 Aprile ore 10:00 in P200
• Terzo appello:
  • scritto: 20 Luglio ore 10:00 in LUM250
  • orale: 27 Luglio ore 10:00 in P200
• Quarto appello:
  • scritto: 13 Settembre ore 10:00 in P200
  • orale: 20 Settembre ore 10:00 in P200

• Automi a stati finiti deterministici e non
  
• Espressioni regolari e automi
  
• Pumping lemma e proprieta' dei linguaggi regolari
  
• Equivalenza e minimizzazione degli automi a stati finiti
• Grammatiche libere da contesto
• Linguaggi regolari e grammatiche
• Automi a pila
• Pumping lemma per linguaggi liberi da contesto
• Macchine di Turing, problemi ricorsivi e ricorsivamente enumerabili.
• Riduzioni e teorema di Rice
• Classi P e NP