Corso di Automi, Linguaggi e
Traduttori (Corso frontale e Corso on-line)
Anno Accademico
2009-2010
Laurea Triennale
in Ingegneria Informatica.
Link to: Automi, Linguaggi e Traduttori. (Corso on-line) (username and
password required)
Teacher: Alberto Pettorossi. You can talk to the teacher
after the lectures or by appointment.
Here is his Curriculum Vitae.
You can send
email messages to the teacher (pettorossi@info.uniroma2.it).
In
your message, please, use the subject: alt2010_CognomeNome_Matricola
or
if
you are an ‘online’ student: alt2010online_CognomeNome_Matricola
Lectures: from 30.11.09 to
06.02.10 (No lectures from 22.12.09 to 06.01.10
inclusive)
Monday
11:30-13:15 Room 03 n.e.
Wednesday 14:00-15:45 Room 03 n.e.
Thursday 09:30-11:15 Room 03
n.e.
Exams and Seminars:
Thursday 11.02.10
15:00 Room 03 n.e. Seminario
didattico-scientifico in preparazione all'esame
Tuesday 16.02.10
15:00 Room 03 n.e. Primo
appello (*)
Wednesday 24.02.10 15:00 Room 06
n.e. Secondo appello (*)
Monday 12.07.10
16:00 Room 07 n.e. Seminario
didattico-scientifico in preparazione all'esame
Tuesday 13.07.10 15:00 Room 07
n.e. Primo appello. Esame scritto per il primo e il secondo appello (*)
Tuesday 27.07.10 15:00 Room 07
n.e. Orale secondo appello (*)
Friday 03.09.10
15:00 Room 05 n.e. Seminario
didattico-scientifico in preparazione all'esame
Wednesday 08.09.10
15:00 Room 06 n.e. Esame scritto per il primo e il secondo appello (*)
Wednesday 15.09.10
15:00 Room 03 n.e. Orale
secondo appello (*)
Le date degli
orali per il primo e il secondo appello saranno comunicate alla fine dell’esame
scritto.
---------------------------------
(*) 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 agli indirizzi:
alt@iasi.cnr.it e pettorossi@info.uniroma2.it
un
messaggio con oggetto: alt2010_CognomeNome_Matricola
con
testo:
Invio in allegato
i miei elaborati per le due prove in itinere che ho fatto da solo/a. 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:
alt2010_CognomeNome_Matricola_CYKParser1
alt2010_CognomeNome_Matricola_LR1Parser2
Se
si è studenti ‘online’:
altonline2010_CognomeNome_Matricola_CYKParser1
altonline2010_CognomeNome_Matricola_LR1Parser2
Non
si includano screenshots e ci si attenga a queste indicazioni, per cortesia.
Si
invii il messaggio di cui sopra con i due allegati, anche se ciò è stato
fatto
per un appello
precedente.
Di
norma non ci si può iscrivere a più di tre appelli per anno accademico.
---------------------------------
Obiettivo
del corso e risultati di apprendimento previsti.
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 dellacomputabilità.
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, indecidibili e
semidecidibili.
Knuth-Morris-Pratt
pattern matcher. Triple di Hoare per la correttezza parziale.
Programma dettagliato del corso e domande
d'esame.
Previous
Exam Questions.
Dispense:
1.
Quantifiers.pdf
2. DistributedTermination.pdf (facoltativo)
3. HsiangTheoremProver.pdf (facoltativo)
4. LeftLinear-RightLinear-Grammars-Conversion.pdf
5. ContextFreeOnSingletonSigma.pdf (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.
La frequenza è obbligatoria.
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.
Dati statistici relativi alle votazioni d’esame
conseguite dagli studenti
------------------------------------------------------------------------------------------------------------
Testi
consigliati.
1. A. Pettorossi: Automata Theory and Formal Languages. Second Edition. Aracne, 2009.
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. Pettorossi: Techniques for Searching, Parsing, and Matching. Second Edition. Aracne, 2009.
Chapter 2.2, 2.3, 4.1, 4.2, 5,
6.1, 6.2.1, 9.1.
Errata Corrige of Books
------------------------------------------------------------------------------------------------------------
Tra i molti
testi disponibili per approfondire gli argomenti del corso, si segnalano i
seguenti:
2. A.V. Aho, R.
Sethi, J.D. Ullman: Compilers: Principles, Techniques, and Tools.
Addison-Wesley, 1986. This
book is also known as "The Dragon Book".
3. J.E. Hopcroft,
R. Motwani, J.D. Ullman: Introduction to Automata Theory, Languages,
and Computation, Addison-Wesley Pub. Co., 2001
(Revised Edition).
4. A.
Pettorossi: Quaderni di Informatica Parte I. Second Edition. Aracne, 2004. Chapters 1 and 8.
5. A.
Pettorossi and M. Proietti: First Order
Predicate Calculus and Logic Programming.
Second Edition. Aracne, 2005.
------------------------------------------------------------------------------------------------------------