Anno di corso: 1

Crediti: 8
Crediti: 8
Crediti: 8
Crediti: 3
Tipo: Lingua/Prova Finale
Crediti: 3
Tipo: Lingua/Prova Finale
Crediti: 3
Tipo: Lingua/Prova Finale
Crediti: 3
Tipo: Lingua/Prova Finale

Anno di corso: 2

Anno di corso: 3

Crediti: 8
Crediti: 8
Crediti: 8
Crediti: 8
Crediti: 16
Tipo: A scelta dello studente
Crediti: 4
Tipo: Lingua/Prova Finale
Crediti: 13
Tipo: Altro

LINGUAGGI E COMPUTABILITA'

Scheda dell'insegnamento

Anno accademico di regolamento: 
2017/2018
Anno di corso: 
2
Anno accademico di erogazione: 
2018/2019
Tipo di attività: 
Obbligatorio
Lingua: 
Italiano
Crediti: 
8
Ciclo: 
Primo Semestre
Ore di attivita' didattica: 
68
Prerequisiti: 

I contenuti degli insegnamenti del primo anno

Moduli

Metodi di valutazione

Modalita' di verifica dell'apprendimento: 

La verifica dell'apprendimento comprende una prova scritta e un colloquio orale, oltre allo svolgimento di alcuni esercizi svolti in laboratorio durante il corso.

Nella prova scritta si richiede di svolgere alcuni esercizi simili a quelli svolti a lezione e presenti sul supporto e-learning del corso e di rispondere ad alcune domande aperte sulla teoria della computabilità. Durante il semestre, verranno svolte due prove scritte in itinere che sostituiscono la prova scritta finale.

Si è ammessi al colloquio orale se è stata superata la prova scritta, o le due prove in itinere, e se sono stati consegnati gli esercizi relativi al laboratorio, così come specificato nel sito del corso. Al colloquio orale, oltre alla discussione dello scritto, possono essere fatte domande sugli argomenti del corso.

Valutazione: 
Voto Finale

Obiettivi formativi

L’insegnamento ha l’obiettivo di mettere in relazione elementi della teoria dei linguaggi formali con le basi dell'analisi lessicale e sintattica dei linguaggi di programmazione e di rendere lo studente consapevole dei limiti della computazione. Lo studente sarà in grado di definire grammatiche regolari e libere da contesto che sono necessarie per l’utilizzo di analizzatori sintattici standard

Contenuti

Automi a stati finiti, linguaggi regolari e espressioni regolari. Linguaggi e grammatiche libere da contesto e automi a pila. Elementi di computabilità: la macchina di Turing; la tesi di Church-Turing; la macchina di Turing Universale. Problemi non risolvibili. Linguaggi di mark-up e di serializzazione e loro relazione con le grammatiche

Programma esteso

Introduzione ai contenuti del corso. I concetti matematici di base per la teoria degli automi
Automi a stati finiti deterministici. Automi a stati finiti non deterministici. Un’applicazione: ricerche testuali. Automi a stati finiti con epsilon-transizioni
Espressioni regolari. Automi a stati finiti ed espressioni regolari
Proprietà del linguaggi regolari. Pumping Lemma per diimostrare che un linguaggio (non) è regolare. Chiusura di linguaggi regolari rispetto ad operazioni booleane. Equivalenza e minimizzazione di automi
Grammatiche. Grammatiche Libere dal Contesto. Alberi sintattici. Applicazioni delle Grammatiche Libere dal Contesto. Ambiguità nelle Grammatiche e nei Linguaggi
Macchine di Turing. Problemi che i calcolatori non possono risolvere. La Macchina di Turing. Estensione alla Macchina di Turing semplice. Macchine di Turing ridotte
Computabilità. Linguaggi non Ricorsivamente Enumerabili. Linguaggi Ricorsivamente Enumerabile e Ricorsivi. Problemi indecidibili relativi alle Macchine di Turing
Analizzatori lessicali e sintattici. Linguaggi di mark-up: XML

Bibliografia consigliata

J.E. Hopcroft, R. Motwani, J.D. Ullman, Automi, linguaggi e calcolabilità, Addison Wesley
Materiale fornito sul supporto e-learning

Metodi didattici

Lezioni, esercitazioni, laboratorio