1 informazioni sul corso §fondamenti dei linguaggi di programmazione: automi (teoria degli automi)...
TRANSCRIPT
![Page 1: 1 Informazioni sul Corso §Fondamenti dei Linguaggi di Programmazione: automi (Teoria degli Automi) §6 crediti §Docente: Francesca Levi (email: levifran@di.unipi.it)](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb4c497959361e8b99a9/html5/thumbnails/1.jpg)
1
Informazioni sul Corso
Fondamenti dei Linguaggi di Programmazione: automi (Teoria degli Automi)
6 crediti Docente: Francesca Levi
(email: [email protected])
![Page 2: 1 Informazioni sul Corso §Fondamenti dei Linguaggi di Programmazione: automi (Teoria degli Automi) §6 crediti §Docente: Francesca Levi (email: levifran@di.unipi.it)](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb4c497959361e8b99a9/html5/thumbnails/2.jpg)
2
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
![Page 3: 1 Informazioni sul Corso §Fondamenti dei Linguaggi di Programmazione: automi (Teoria degli Automi) §6 crediti §Docente: Francesca Levi (email: levifran@di.unipi.it)](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb4c497959361e8b99a9/html5/thumbnails/3.jpg)
3
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
![Page 4: 1 Informazioni sul Corso §Fondamenti dei Linguaggi di Programmazione: automi (Teoria degli Automi) §6 crediti §Docente: Francesca Levi (email: levifran@di.unipi.it)](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb4c497959361e8b99a9/html5/thumbnails/4.jpg)
4
Orario delle Lezioni
Mercoledi’: 11-13 B1Venerdi’: 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
![Page 5: 1 Informazioni sul Corso §Fondamenti dei Linguaggi di Programmazione: automi (Teoria degli Automi) §6 crediti §Docente: Francesca Levi (email: levifran@di.unipi.it)](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb4c497959361e8b99a9/html5/thumbnails/5.jpg)
5
Informazioni sul CorsoPossibili variazioni d’orario, materiale didattico
www.di.unipi.it/~levifran/FA.html
Ricevimento: martedi’ dalle 14.00 alle 16.00
![Page 6: 1 Informazioni sul Corso §Fondamenti dei Linguaggi di Programmazione: automi (Teoria degli Automi) §6 crediti §Docente: Francesca Levi (email: levifran@di.unipi.it)](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb4c497959361e8b99a9/html5/thumbnails/6.jpg)
6
Modalita’ d’EsameA 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
![Page 7: 1 Informazioni sul Corso §Fondamenti dei Linguaggi di Programmazione: automi (Teoria degli Automi) §6 crediti §Docente: Francesca Levi (email: levifran@di.unipi.it)](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb4c497959361e8b99a9/html5/thumbnails/7.jpg)
7
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’
![Page 8: 1 Informazioni sul Corso §Fondamenti dei Linguaggi di Programmazione: automi (Teoria degli Automi) §6 crediti §Docente: Francesca Levi (email: levifran@di.unipi.it)](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb4c497959361e8b99a9/html5/thumbnails/8.jpg)
8
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
![Page 9: 1 Informazioni sul Corso §Fondamenti dei Linguaggi di Programmazione: automi (Teoria degli Automi) §6 crediti §Docente: Francesca Levi (email: levifran@di.unipi.it)](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb4c497959361e8b99a9/html5/thumbnails/9.jpg)
9
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
![Page 10: 1 Informazioni sul Corso §Fondamenti dei Linguaggi di Programmazione: automi (Teoria degli Automi) §6 crediti §Docente: Francesca Levi (email: levifran@di.unipi.it)](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb4c497959361e8b99a9/html5/thumbnails/10.jpg)
10
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.
![Page 11: 1 Informazioni sul Corso §Fondamenti dei Linguaggi di Programmazione: automi (Teoria degli Automi) §6 crediti §Docente: Francesca Levi (email: levifran@di.unipi.it)](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb4c497959361e8b99a9/html5/thumbnails/11.jpg)
11
Programma: seconda parteAutomi temporizzati e probabilisticiAutomi concorrentiL-sistemiP-systemStrumenti 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
![Page 12: 1 Informazioni sul Corso §Fondamenti dei Linguaggi di Programmazione: automi (Teoria degli Automi) §6 crediti §Docente: Francesca Levi (email: levifran@di.unipi.it)](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb4c497959361e8b99a9/html5/thumbnails/12.jpg)
12
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.