Corso di Automi, Linguaggi e Traduttori.  Laurea on-line.

Anno Accademico 2004-2005.


Dipartimento di Informatica, Sistemi e Produzione. Computer Science Department.

Link to Ingegneria On line
(password required)
Link to Ingegneria On line: Automi, Linguaggi e Traduttori
(password required)

Docente: Alberto Pettorossi. You can talk to the teacher by appointment.
You can send email messages to the teacher.
Please, in your email messages use the subject: ALTonline2004-5 NomeCognome NumeroDiMatricola

Lectures: from 07.03.2005 to 29.04.2005.
Exams: prova finale e prova di recupero nel periodo 2-13.05.2005
Exam dates: 
     zzzzzzday xx.yy.zz  hh:mm   (Room xx n.e.)
(Information to be updated)
     zzzzzzday xx.yy.zz  hh:mm   (Room xx n.e.) (Information to be updated)

Obiettivo del corso.
Introduzione alla gerarchia dei linguaggi formali e degli automi con
particolare riferimento ai linguaggi regolari, ai linguaggi liberi
dal contesto, agli automi finiti e agli automi pushdown. Introduzione alle
tecniche fondamentali per l'analisi sintattica e la compilazione dei
linguaggi di programmazione.

Programma del corso:
Preliminari matematici. Gerarchia di Chomsky. Linguaggi regolari,
espressioni regolari, automi finiti. Parsing dei linguaggi regolari.
Linguaggi liberi dal contesto e automi pushdown. Parsing dei linguaggi
liberi dal contesto: Cocke-Younger-Kasami parser, chop-expand parser,
LL-parsers (facoltativo), LR-parsers (facoltativo). LALR(k) parsers (facoltativo).

Prerequisiti: Elementi di programmazione in C++ o in Java.
Uso di arrays, liste, puntatori e ricorsione.
Elementi di Algebra e di Calcolo dei Predicati. 

Prove in itinere.
Programma dettagliato del corso e domande d'esame.
Modalità di esame:
 

Presentazione e discussione degli esercizi delle prove in itinere (da svolgere individualmente).
Scritto e orale.
Si ricorda che possono sostenere l'esame solo gli studenti che:
(i) nell'anno accademico 2004-05 sono iscritti al secondo anno ripetente o al terzo anno o al terzo anno ripetente, e
(ii) hanno presentato il piano di studi per l'anno 2004-05, e
(iv) hanno optato per il corso di Automi, Linguaggi e Traduttori (essendo il corso in alternativa ad altri corsi), e
(iii) se iscritti per l'anno accademico 2004-05 al secondo anno ripetente, allora hanno richiesto nel piano di studi di anticipare il corso di Automi, Linguaggi e Traduttori al secondo anno, e
(v) hanno avuto il piano di studi approvato.

Norme generali di accesso agli esami:
-------------------------------------
1) Non è possibile sostenere un esame che, per conflitto col piano di studi o con l'anno di iscrizione,
non possa esser sostenuto
dallo studente nell'anno in corso.
2) Lo studente dovrà presentarsi all'esame
con il libretto di iscrizione e con una copia approvata del proprio piano
di studi (autentica
rilasciata dalla segreteria studenti).
---------------------------------------------------------------------------------------------------------------------

Testi consigliati.
1. J. E. Hopcroft, R. Motwani, J.D. Ullman: "Automi, Linguaggi e Calcolabilita`", Addison-Wesley,
    Pearson Education Italia, 1997.

2. Pettorossi, A.: Theory of Computation II.  (2nd Edition) Aracne (1993).
3. Pettorossi, A.: Theory of Computation III. (2nd Edition) Aracne (1994).
4. Pettorossi, A.: Programming in C++. Aracne, 2001.
-------------------------------------------------------------