| | | corso | | | |
Fondamenti dei linguaggi di programmazione: automi
Codice: | AA619 | Crediti: | 6 | Semestre: | 1 | Sigla: | FA | |
|
Settore disciplinare: | INF/01 - Informatica |
Docente
Francesca Levi
Tel. 0502212770Ultima versione disponibile: programma da confermare per l’a.a. 2008/2009
Obiettivi di apprendimento
Obiettivo del corso è l'esposizione dei concetti di base della teoria degli automi e dei linguaggi formali e l’ introduzione
a formalismi più recenti proposti per descrivere sistemi complessi, naturali e artificiali.
Descrizione
La teoria degli automi e dei linguaggi formali è alla base della descrizione dei linguaggi di programmazione,
della costruzione dei loro riconoscitori e traduttori, della realizzazione di strumenti di elaborazione testuale.
Applicazioni si hanno oggi in molti campi, includendo la biologia, la botanica e lo studio dei sistemi concorrenti
e distribuiti. Il corso fornirà definizioni di base e proprietà. Introdurrà L-sistemi, proposti per descrivere sistemi
biologici, automi temporizzati, interessanti per descrivere sistemi che reagiscono a un ambiente che invia segnali
con vincoli di tempo, e modelli utili per descrivere sistemi gerarchici e concorrenti. Si presenteranno anche
strumenti automatici che verranno utilizzati per sviluppare specifiche e prove per casi di esempio.
English Description
The theory of automata and formal languages is at the basis of the description of programming languages,
of the construction of parsers and translators, of the realization of text-processing tools. The theory has applications
in many fields, including biology, botany, and the study of concurrent and distributed systems. The course will
supply basic definitions and properties. Also L-systems, proposed to model biological systems, timed automata,
useful for the description of reactive systems with time constraints, and models suitable to describe concurrent
hierarchical systems will be introduced. Automatic tools for specification and verification of properties will be
also described and used to develop specifications and verifications for sample cases.
Programma
Automi a stati finiti. Espressioni regolari.
Proprietà degli insiemi regolari. (8 ore)
Grammatiche non contestuali. Automi a pila.
Proprietà dei linguaggi non-contestuali. (8 ore)
Linguaggi contestuali. Grammatiche non ristrette.
La gerarchia di Chomsky. (6 ore)
L-sistemi. (4 ore)
Automi temporizzati. Automi gerarchici.
Automi concorrenti. (16 ore)
Strumenti software di specifica e verifica. (6 ore)
Ore lezione: | 34 | Ore esercitazione: | 14 | | | |
Bibliografia
Hopcroft J.E., Ullman J.D., Introduction to Automata Theory, Languages, and Computation, Addison Wesley, Reading, Mass., 1979.
Hopcroft J.E., Motwani, R., Ullman J.D.,
Automi, linguaggi e calcolabilità,
Addison Wesley, Pearson Education Italia, 2003.
Alur R., Dill D.L.,
A Theory of Timed Automata,
Theoretical Computer Science 126 (1994) 183-225.
Salomaa, A., Formal Languages, Academic Press, New York, 1987.
Modalità di esame
A scelta dello studente esame orale su tutti gli argomenti del corso o seminario
che sviluppi un argomento scelto tra quelli trattati o progetto che
utilizzi uno degli strumenti software esaminati.