Home » Archivo » Archvio 2009 » Automi e linguaggi formali - 2009/2010

Laurea in Informatica

Salta il menu di secondo livello

Automi e linguaggi formali - 8 CFU - A.A. 2009/2010

Insegnante

Prof. Francesca Rossi

Periodo

II anno - 2 trimestre | 11/01/2010 - 12/03/2010

Ore: 48 Frontali, 0 Laboratorio, 16 Esercizi

Torna su ▲

Programma del Corso

Gli argomenti principali del corso sono:

Parte 1: linguaggi regolari e analisi lessicale (3 cfu)
-- automi a stati finiti
-- espressioni e linguaggi regolari
-- analisi lessicale

Parte 2: linguaggi liberi da contesto e analisi sintattica (3 cfu)
-- grammatiche e linguaggi liberi dal contesto
-- automi a pila
-- analisi sintattica: parsers top-down (LL) e bottom-up (LR)

Parte 3: indecidibilita' e intrattabilita' (2 cfu)
-- macchine di Turing
-- concetto di indecidibilita'
-- problemi intrattabili
-- classi P e NP

Prerequisiti: Logica

Propedeuticità: - -

Ausili Didattici:

Testi di Riferimento: -- Automi, Linguaggi e calcolabilita'
J. E. Hopcroft, R. Motwani, J. D. Ullman, Addison Wesley, 2003.
-- Compilers: Principles, Techniques, and Tools (2nd Edition)
Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman, Addison-Wesley 2006.
-- Programming Languages: Design and Implementation. Third Edition. Prentice Hall, 1996. T.W. Pratt and M.V. Zelkiwitz.

Torna su ▲