1. Programma del corso	4. Orario lezioni e ricevimento
2. Testi consigliati e dispense	5. Prossimi appelli
3. Modalità d'esame	6. Date degli appelli d'esame per l'a.a. 2002/2003

PROGRAMMA DEL CORSO

• Generalità sui linguaggi formali
  Nozioni di base: monoidi liberi, linguaggi, grammatiche, derivazioni. Grammatiche dipendenti da contesto, libere da contesto, regolari e le relative classi di linguaggi.
  

• Linguaggi regolari
  Automi a stati finiti deterministici e non deterministici. Grammatiche regolari e automi a stati finiti. Espressioni regolari. Teorema di Kleene. Lemma di iterazione per linguaggi regolari. Congruenze sintattiche e costruzione degli automi minimi. Il problema di string matching e i relativi algoritmi basati su automi a stati finiti.
  Strumenti di manipolazione dei testi basati su automi a stati finiti ed espressioni regolari: grep e programmi derivati (awk, sed, perl). Proprietà del linguaggio XML legate ai linguaggi regolari: parsing superficiale.
  

• Linguaggi liberi da contesto
  Alberi di derivazione. Semplificazioni delle grammatiche libere da contesto. Forma normale di Chomsky. Algoritmo di riconoscimento di Cocke-Kasami-Young. Il lemma di iterazione per i linguaggi liberi da contesto. La forma normale di Greibach. Automi a pila deterministici e non deterministici. Caratterizzazione dei linguaggi liberi da contesto mediante automi a pila. Proprietà di chiusura dei linguaggi liberi da contesto. Cenni alle grammatiche non ambigue e ai linguaggi liberi da contesto inerentemente ambigui.
  Proprietà del linguaggio XML legate ai linguaggi context-free: regole di annidamento e documenti ben formati. Strumenti per la creazione di parser: Java Compiler-Compiler. Parsing e costruzione automatica degli alberi sintattici XML in Java tramite Xerces.

TESTI CONSIGLIATI E DISPENSE

• Dispense tratte dalle lezioni del Prof. Goldwurm, tenute nell'a.a. 2001/2002, realizzate dagli studenti Marco Alfieri, Matteo Bianchi, Grazia D'Aversa, Andrea Fumagalli, Emanuele Mornini, Dario Villa e Massimo Vitali, disponibili presso gli indirizzi seguenti: file pdf, file zip in formato ps.

• Appunti delle lezioni del Prof. Goldwurm tenute nell'a.a. 2001/2002, curati dagli studenti Luca Benelli e Andrea Gimignani, disponibili presso l'indirizzo: file word.

• J.E. Hopcroft, R. Motwani, J.D. Ullman,
  Introduction to automata theory, languages and computation,
  Addison-Wesley, 2001.
  Di questo testo esiste una versione precedente, a firma solo di J.E. Hopcroft e J.D. Ullman, pubblicata nel 1979 dallo stesso editore.

• E. Kimber, C. Smith,
  Theory of computing, a gentle introduction,
  Prentice Hall, 2001.

• J.E. Hopcroft, J.D. Ullman,
  Formal languages and their relation to automata,
  Addison-Wesley, 1969.

• M. Harrison,
  Introduction to formal language theory,
  Addison-Wesley, 1978.

• E. Rusty Harold, W. Scott Means,
  XML ina Nutshell, a Desktop Quick Reference,
  O'Reilly, January 2001, 0-596-00058-8, 492 pages.

• C.F. Goldfarb, P. Prescod,
  The XML handbook,
  Prentice Hall, 1998.

• Per gli argomenti legati al compilatore di parser in Java si veda anche JAVA CC .

• Per gli argomenti legati a XML e al suo parser si veda anche definizione XML e XERCES 2 .

MODALITÀ D'ESAME

ORARIO DELLE LEZIONI

Turno 1

Le lezioni si terranno in aula V3 presso la Didatteca di via Venezian 15.

• Lunedì, ore 8.30-10.30 ;
• Venerdì, ore 8.30-10.30 .

ORARIO DI RICEVIMENTO

PROSSIMA PROVA

L'ultimo appello relativo all'anno accademico 2002/2003 (turno Prof. Goldwurm) si svolgerà martedì 8 Gennaio 2004 alle ore 9.30 in auletta 4 presso il DSI, via Comelico 39, Milano.
Gli studenti interessati sono pregati di iscriversi inviando un messaggio di posta elettronica a goldwurm@dsi.unimi.it.

DATE DEGLI APPELLI D'ESAME PER L'A.A. 2002/2003