| | | corso | | | |
Fondamenti dei linguaggi di programmazioni: automi
Codice: | AA424 | Crediti: | 3 | Semestre: | 2 | Sigla: | FA | |
|
Settore disciplinare: | INF/01 - Informatica |
Docente
Andrea Maggiolo Schettini
Tel. 0502212700Obiettivi di apprendimento
L' esposizione dei concetti di base della teoria degli automi e dei linguaggi formali e una breve introduzione a formalismi più recenti.
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 sistemi a transizioni, utili per descrivere sistemi gerarchici e concorrenti.
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 transition systems suitable to describe concurrent hierarchical systems will be introduced.
Programma
- Automi a stati finiti. Espressioni regolari. Proprietà degli insiemi regolari. (6 ore)
- Grammatiche non contestuali. Automi a pila. Proprietà dei linguaggi non-contestuali. (6 ore)
- Linguaggi contestuali. Grammatiche non ristrette. Relazioni tra classi di linguaggi. La gerarchia di Chomsky. (2 ore)
- L-sistemi. (2 ore)
- Automi temporizzati. (4 ore)
- Statecharts (4 ore)
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.
- Salomaa, A., Formal Languages, Academic Press, New York, 1987.
- Alur R., Dill D.L., A Theory of Timed Automata, Theoretical Computer Science 126 (1994) 183-225.
- Harel, D, A visual formalism for complex systems, Science of Computer programming 8 (1987) 271-274.
Modalità di esame
Esame orale