Informazioni sul Corso
 Fondamenti dei Linguaggi di
Programmazione: automi (Teoria degli
Automi)
 6 crediti
 Docente: Francesca Levi
(email: [email protected])
1
Nota 1
 Corso Complementare della Laurea Specialistica di
Informatica (vecchio ordinamento)
 Parte del programma di questo corso verra’ coperto dal
nuovo corso di Calcolabilita’ e Complessita’ della nuova
Laurea Triennale in Informatica a partire dal prossimo
anno accademico
 Questo corso non fa parte di nessun piano di studi delle
nuove lauree magistrali
2
Nota 2
 A partire dal prossimo anno accademico il corso verra’
soppresso (non si terranno piu’ le lezioni)
 Rimane la possibilita’ di svolgere gli esami per i prossimi
tre anni accademici
3
Orario delle Lezioni
 Mercoledi’: 11-13 B1
 Venerdi’: 9-11C
 Eventuali variazioni d’orario possono essere
valutate solo se richieste da un numero consistente
di studenti, a patto di avere trovato la
disponibilita’ di un’ aula
4
Informazioni sul Corso
 Possibili variazioni d’orario, materiale didattico
www.di.unipi.it/~levifran/FA.html
 Ricevimento: martedi’ dalle 14.00 alle 16.00
5
Modalita’ d’Esame
A scelta dello studente esame orale su tutti gli argomenti del corso
o seminario che approfondisca uno degli argomenti trattati a lezione
•In entrambi i casi gli esami dovranno svolgersi nei periodi di appello
d’esame standard con le seguenti modalita’:
(1) orale su appuntamento
(2) seminario su appuntamento o in date fissate, che verranno
rese note alla fine delle lezioni
Per iscriversi si prega di inviare sempre la richiesta per e-mail con almeno
una settimana di anticipo
6
Contenuti del corso
 La Teoria degli Automi e’ uno degli argomenti di base
dell’informatica teorica
 Tradizionalmente, studiare dispositivi astratti di calcolo
o “macchine”
 Negli anni ‘30, Turing studio’ una macchina astratta che
fornisce un modello della capacita’ dei computer reali
 Tali macchine permettono di distinguere i problemi
decidibili e non decidibili, ed i problemi trattabili ed
intrattabili
 Insieme ai lavori di Cook degli anni ‘60, la base della
teoria della calcolabilita’ e della complessita’
7
Linguaggi Formali
 Linguaggi intesi in senso sintattico come insiemi di
stringhe (inclusi quelli che definiscono i linguaggi di
programmazione)
 Negli anni ‘40,’50 alcuni ricercatori studiarono dei tipi
particolari di macchine, dette automi a stati finiti, che
permettono di definire alcune classi di linguaggi formali
 Parallelamente, Chomsky studio’ le grammatiche
formali e le loro proprieta’
 In questo corso ci occuperemmo dei linguaggi formali,
dei vari approcci per definire e riconoscere linguaggi,
delle loro proprieta’ e delle relazioni tra i vari approcci
8
Perche’ studiare TDA?
 Alcuni dei concetti teorici che studieremo nel corso sono
alla base di importanti tipi di software
 Costruzione dei riconoscitori e traduttori per i linguaggi
di programmazione (compilatori): realizzazione del
parser, analisi lessicale
 Software per la verifica di correttezza di circuiti o
protocolli
 Realizzazione di strumenti di elaborazione testuale
 Strumenti per la specifica e la verifica di sistemi
concorrenti, probabililistici e sistemi biologici
(solo per menzionare alcune applicazioni)
 Non studieremo le applicazioni ma i risultati teorici
 Alcune applicazioni potranno per esempio essere
argomenti di seminari
9
Programma: prima parte






Automi a stati finiti. Espressioni regolari.
Proprietà degli insiemi regolari.
Grammatiche libere dal contesto. Automi a pila.
Proprietà dei linguaggi liberi dal contesto.
Linguaggi contestuali. Grammatiche non ristrette.
La gerarchia di Chomsky.
10
Programma: seconda parte
 Automi temporizzati e probabilistici
 Automi concorrenti
 L-sistemi
 P-system
 Strumenti software di specifica e verifica.
 Questi sono argomenti che potrebbero essere
trattati (quali dipende dal tempo, come andranno
le lezioni)
 Potrebbero essere argomenti di seminari
11
Libri di Testo

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.
12