Teoria dei linguaggi

A.A. 2020/2021
6
Crediti massimi
48
Ore totali
SSD
INF/01
Lingua
Italiano
Obiettivi formativi
Obiettivo dell'insegnamento è la presentazione delle basi della teoria dei linguaggi formali e degli automi, insieme a sviluppi recenti e problemi aperti significativi.
Risultati apprendimento attesi
Lo studente dovrà essere in grado di utilizzare la teoria dei linguaggi formali e degli automi per descrivere formalmente la sintassi di semplici linguaggi artificiali, come i linguaggi di programmazione, o di semplici modelli di calcolo. Dovrà inoltre essere in grado di stabilire confronti tra modelli formali differenti, sia rispetto alla potenza computazionale, sia rispetto alla complessità delle descrizioni.
Programma e organizzazione didattica

Edizione unica

Responsabile
Periodo
Secondo semestre
Programma
L'insegnamento è dedicato alla teoria degli automi e dei linguaggi formali. Verranno presentati i principali risultati relativi alle classi di linguaggi della gerarchia di Chomsky e dei corrispondenti modelli di macchine, riprendendo e approfondendo quanto trattato nel corso di Linguaggi Formali e Automi. Sarà posto particolare accento sullo studio delle risorse computazionali necessarie per il riconoscimento delle diverse classi di linguaggi e, più in generale, agli aspetti di complessità descrizionale. Alcune lezioni saranno dedicate alla discussione di sviluppi recenti ottenuti nelle ricerche nel settore, nonché a problemi aperti.

Gli argomenti principali trattati sono:
- Automi a stati finiti, linguaggi regolari e complessità descrizionale. Tecniche di lower bound per il numero di stati di automi deterministici e non deterministici. Operazioni su linguaggi regolari e loro complessità in termini di stati. Automi e matrici. Alcuni aspetti degli automi pesati e probabilistici. Automi two-way w il problema di Sakoda e Sipser.
- Automi a pila e linguaggi liberi dal contesto. Determinismo e non determinismo. Pumping lemma, lemma di Ogden e applicazioni. Il problema dell'ambiguità nei linguaggi liberi dal contesto. Esistenza di linguaggi inerentemente ambigui. Principali proprietà di chiusura e non chiusura della classe dei linguaggi liberi dal contesto e della sottoclasse dei linguaggi liberi dal contesto deterministici. Grammatiche non self-embedding e regolarità della corrispondente classe di linguaggi.
- Altre classi della gerarchia di Chomsky. Uno sguardo ad alcune proprietà dei linguaggi dipendenti dal contesto, dei linguaggi di tipo 0 e dei corrispondenti modelli di calcolo.

Un elenco dettagliato degli argomenti trattati, lezione per lezione, viene pubblicato e aggiornato sul sito web dell'insegnamento.
Prerequisiti
E' richiesta la conoscenza delle nozioni fondamentali relative agli automi a stati finiti, linguaggi regolari e automi a pila, presentate nell'insegnamemto di Linguaggi Formali e Automi della laurea triennale in Informatica o in insegnamenti analoghi di altri corsi di studio.
Metodi didattici
Lezioni frontali.
Materiale di riferimento
Sito web dell'insegnamento:
https://gpighizzinitl.ariel.ctu.unimi.it/

Riferimenti bibliografici:
J. Shallit, A Second Course in Formal Languages and Automata Theory. Cambridge University Press, 2009
J. Hopcroft and J. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979 - Nota: nelle edizioni successive (2000, 2006, ed. italiana 2009), più orientate a corsi di base, molti argomenti sono stati eliminati o sono in modo meno approfondito.
J. Hopcroft and J. Ullman, Formal languages and their relation to automata. Addison Wesley, 1969 - Nota: "Precursore" del libro del 1979. Ben scritto, ma poco aggiornato su alcuni argomenti. Scaricabile dalla ACM Digital Library (dalla rete all'interno dell'università).
Modalità di verifica dell’apprendimento e criteri di valutazione
L'esame consiste di una prova orale, relativa agli argomenti trattati nell'insegnamento.
La valutazione, espressa in trentesimi, tiene conto del livello di padronanza degli argomenti, della chiarezza espositiva e della proprietà di linguaggio.
INF/01 - INFORMATICA - CFU: 6
Lezioni: 48 ore
Docente/i
Ricevimento:
A causa dell'emergenza sanitaria, al momento il ricevimento studenti viene svolto a distanza. Consultare la pagina http://pighizzini.di.unimi.it/ricevimento.html per dettagli e informazioni aggiornate
Ricevimento:
Da concordare via e-mail
Dipartimento di Informatica - via Celoria, 18 - Stanza 5022 (quinto piano)