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

Laurea in Informatica

Salta il menu di secondo livello

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

Sito per la parte di automi e linguaggi formali

Insegnante

Prof. Francesca Rossi

Periodo

II anno - 1 trimestre | 18/10/2010 - 11/12/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.
Logic.

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 ▲