Anno Accademico 2005-2006.

Docente: Alberto Pettorossi. You can talk to the teacher by appointment or after the lectures.
In case of urgent need, you can send email messages to the teacher. 
In your messages, please, use the subject: alt2006_CognomeNome_Matricola

Lectures:  from 12.12.05 to 16.02.06         (No lectures from 23.12.05 to 08.01.06) 
           Monday   16:00-17:45  Room 2 PP2 
           Tuesday  11:30-13:15  Room 2 PP2
           Thursday 11:30-13:15  Room 2 PP2   

---------------------------------
(*) Prenotarsi nel foglio predisposto all'ingresso dell'edificio
di Ingegneria dell'Informazione (Via del Politecnico 1, 00133 Roma)
entro sette giorni prima della 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 prima della data dell'appello a:
corsoalt2006@tiscali.it e a pettorossi@info.uniroma2.it
un messaggio con oggetto: alt2006_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 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:
           alt2006_CognomeNome_Matricola_Membership1
           alt2006_CognomeNome_Matricola_Parsing2
Se si e` studenti "online":
           altonline2006_CognomeNome_Matricola_Membership1
           altonline2006_CognomeNome_Matricola_Parsing2
--> Non si includano screenshots e ci si attenga a queste indicazioni, per cortesia.
--> Si invii il messaggio con i due file 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 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 liberi dal contesto e automi pushdown deterministici e nondeterministici.
Parsing dei linguaggi liberi dal contesto: Cocke-Younger-Kasami parser, chop-expand parser,
Earley's parser, LL-parsers, LR(0) parsers, LR(1) parsers. LALR(1) parsers.
Macchina di Turing: definizioni fondamentali (vedasi da pagina 3 a pagina 9
della dispensa: Macchina di Turing). KMP pattern matcher.

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

Theorem Prover in C++.
Parser for Regular Languages and Chop Expand Parser  in C++
Chop Expand Parser  in Java 1.5
Knuth-Morris-Pratt algorithm in Java 1.5

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.
---------------------------------------
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.
------------------------------------------------------------------------------------------------------------

Testi consigliati.
1. 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).
Alcune sezioni dei seguenti testi:
2. Pettorossi, A.: Quaderni di Informatica Parte I. (2nd Edition) (2004).
3. Pettorossi, A.: Theory of Computation II.  (2nd Edition) Aracne (1993).
4. A.V. Aho, R. Sethi, J.D. Ullman: Compilers: Principles, Techniques, and Tools.
   Addison-Wesley 1986 (It is the so-called "Dragon Book") Chapter 4.
-------------------------------------------------------------