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

Laurea in Informatica

Salta il menu di secondo livello

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

Sito per la parte di automi e linguaggi formali

Insegnante

Prof.ssa Francesca Rossi

Periodo

II anno - 1 trimestre | 03/10/2011 - 10/12/2011

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 ▲