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

Anno Accademico 2007-2008. 

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

Link to: Automi, Linguaggi e Traduttori. (Corso on-line)   (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: alt2008_CognomeNome_Matricola  or

if you are an online student: alt2008online_CognomeNome_Matricola

 

Lectures:  from 10.12.07 to 15.02.08           (No lectures from 22.12.07 to 06.01.08) 
           Tuesday   11:30-13:15  Room 2 PP2 
           Thursday 11:30-13:15  Room 2 PP2
           Friday      14:00-15:45  Room 4 PP2   

Exams:    

           Tuesday  19.02.08   16:00  (Room 04 n.e.) Seminario didattico-scientifico in preparazione all'esame

           Friday     22.02.08   16:00  (Room 02 n.e.) Primo appello    (*) 

           Tuesday  26.02.08   16:00  (Room 02 n.e.) Secondo appello (*)

 

           Tuesday   09.09.08   16:00  (Room 06 n.e.) Seminario didattico-scientifico in preparazione all'esame
           Thursday 11.09.08   15:30  (Room 02 n.e.) Primo appello    (*)
           Tuesday   16.09.08   15:30  (Room 02 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 può prenotare a entrambi gli appelli.
Se si è 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: alt2008_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:
          
alt2008_CognomeNome_Matricola_ Parsing1
          
alt2008_CognomeNome_Matricola_ Membership2
Se si e` studenti "online":  
  
           altonline2008_CognomeNome_Matricola_Parsing1
          
altonline2008_CognomeNome_Matricola_Membership2

Non si includano screenshots e ci si attenga a queste indicazioni, per cortesia.
Si invii il messaggio con i due allegati, anche se ciò è 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. Problemi decidibili e semidecidibili.
KMP pattern matcher.  Knuth-Morris-Pratt pattern matcher. 
Triple di Hoare per la correttezza parziale.

Prove in itinere. 

Programma dettagliato del corso e domande d'esame.

Previous Exam Questions.
 

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

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.  
1. Pettorossi, A.: Automata Theory and Formal Languages.  Aracne, 2007.
   
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.
Errata Corrige of Books
--------
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.
 -------------------------------------------------------------