Teoria dei linguaggi

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 e 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.