Corso di Automi, Linguaggi e Traduttori  (Corso frontale e Corso on-line)

Anno Accademico 2006-2007. 

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

Link to: Automi, Linguaggi e Traduttori. Laurea on-line 
             (here: username and password required)
Docente: Alberto Pettorossi. You can talk to the teacher after the lectures or by appointment.
You can send email messages to the teacher. In your messages, please,
use the subject: alt2007_CognomeNome_Matricola  or
if you are an online student: alt2007online_CognomeNome_Matricola

Lectures:  from 11.12.06 to 16.02.07         (No lectures from 23.12.06 to 07.01.07) 
           Monday   16:00-17:45  Room 2 PP2 
           Tuesday  11:30-13:15  Room 2 PP2
           Thursday 11:30-13:15  Room 2 PP2   

Exams:     22.02.07   16:00  (Room 06 n.e.) Seminario didattico-scientifico in preparazione all'esame
           27.02.07   16:00  (Room 11 n.e.) Primo appello   (*)
           01.03.07   16:00  (Room 06 n.e.) Secondo appello (*)

                      Tuesday    18.09.07   16:30  (Room 09 n.e.) Seminario didattico-scientifico in preparazione all'esame
           Thursday   20.09.07   10:00  (Room 06 n.e.) Primo appello   (*)
           Tuesday    25.09.07   10:00  (Room 06 n.e.) Secondo appello (*)
---------------------------------
(*) Prenotarsi nel foglio predisposto all'ingresso dell'edificio
di Ingegneria dell'Informazione (Via del Politecnico 1, 00133 Roma)
entro sette giorni dalla data dell'appello.
--> Non ci si puo` prenotare a entrambi gli appelli.
Se si e` studenti "online" nella prenotazione indicare: online.

Inviare entro sette giorni dalla data dell'appello a:
alt@iasi.cnr.it e a pettorossi@info.uniroma2.it
un messaggio con oggetto: alt2007_CognomeNome_Matricola
con testo: Invio in allegato i miei elaborati relativi alle due prove in itinere che ho fatto da solo. Nome Cognome
e con allegati due file di tipo testo (.cpp oppure .java oppure .txt) con i programmi documentati,
con indicazioni per la loro compilazione ed esecuzione, e
con alcune prove di esecuzione riportate come commenti nel codice,
fatti dallo studente, relativi alle prove in itinere. I nomi dei due file siano:
           alt2007_CognomeNome_Matricola_Membership1
           alt2007_CognomeNome_Matricola_Parsing2
Se si e` studenti "online":
           altonline2007_CognomeNome_Matricola_Membership1
           altonline2007_CognomeNome_Matricola_Parsing2
--> Non si includano screenshots e ci si attenga a queste indicazioni, per cortesia.
--> Si invii il messaggio con i due allegati, anche se cio` e` stato fatto per un appello precedente.
---------------------------------
Obiettivo del corso.
Introduzione ai linguaggi formali e agli automi con particolare riferimento
ai linguaggi regolari, ai linguaggi liberi dal contesto, agli automi finiti e
agli automi pushdown. Introduzione alla teoria della  computabilità.
Introduzione alle tecniche fondamentali per l'analisi sintattica e
la compilazione dei linguaggi di programmazione.

Programma del corso:
Preliminari matematici: relazioni, funzioni. Gerarchia di Chomsky. Linguaggi regolari,
espressioni regolari, automi finiti deterministici e nondeterministici. Parsing dei linguaggi regolari.
Linguaggi context-free e automi pushdown deterministici e nondeterministici.
Parsing dei linguaggi context-free: Cocke-Younger-Kasami parser, chop-expand parser,
Earley parser (facoltativo), LL(1) parsers, LR(0) parsers, LR(1) parsers. LALR(1) parsers.
Macchina di Turing e grammatiche di tipo 0 e 1. KMP pattern matcher.

Prove in itinere. 

Programma dettagliato del corso e domande d'esame.

Previous Exam Questions.
 
Dispense:
1. Visiting Trees While Looking for Good Nodes       2. Chop Expand Parser  in Java
3. Chop Expand Parser  in Prolog       4. LL(1) Parsing       5. Theorem Prover in Java
6. Knuth-Morris-Pratt algorithm in Java 1.5         7. Quantifiers        8. Dijkstra's SSSP
9. DistributedTermination      10. LALR(1) parsing using Bison     11. HsiangTheoremProver

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

Modalità di esame: 
Presentazione e discussione degli esercizi delle prove in itinere (da svolgere da soli!).  Scritto e orale.
Lo studente dovrà presentarsi all'esame con il libretto di iscrizione.
------------------------------------------------------------------------------------------------------------
Testi consigliati.   Errata Corrige of Books
1. Pettorossi, A.: Automata Theory and Formal Languages.  Aracne, 2006.
    Escluse le sezioni: 1.6, 2.7, 2.11, 3.13.2, 3.14, 3.15, 3.16, 6.2, 6.3, 6.4, 7.1, 7.2, 7.6.
    e le prove dei teoremi dei capitoli 4, 5 e della sezione 6.1
2. A.V. Aho, R. Sethi, J.D. Ullman: Compilers: Principles, Techniques, and Tools.
   Addison-Wesley, 1986. This book is known as "The Dragon Book".
   The following sections only:
   4.4 (Top-Down Parsing), 4.5 (Bottom-Up Parsing), 4.7 (LR-Parsers). Handouts are available for this part
   of the course.
--------
Tra i tanti testi disponibili ove approfondire alcuni argomenti del corso, si segnalano i seguenti:
3.  J. E. Hopcroft, R. Motwani, J.D. Ullman: "Automi, Linguaggi e Calcolabilità", Addison-Wesley,
    Pearson Education Italia, 1997. In Inglese: "Introduction to Automata Theory, Languages,
    and Computation, Addison-Wesley Pub. Co., 2001 (Revised Edition).
4.  Pettorossi, A.: Quaderni di Informatica Parte I. 2nd Edition, Aracne, 2004. In particular, Chapters 1 and 8.
 -------------------------------------------------------------