1

Informazioni sul Corso

Fondamenti dei Linguaggi di Programmazione: automi (Teoria degli Automi)

6 crediti Docente: Francesca Levi

(email: levifran@di.unipi.it)

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

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

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

5

Informazioni sul CorsoPossibili variazioni d’orario, materiale didattico

www.di.unipi.it/~levifran/FA.html

Ricevimento: martedi’ dalle 14.00 alle 16.00

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

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’

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

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

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.

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

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.