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: 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: 
2014/2015
Anno di corso: 
2
Anno accademico di erogazione: 
2015/2016
Tipo di attività: 
Obbligatorio
Crediti: 
8
Ciclo: 
Primo Semestre
Ore di attivita' didattica: 
70
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 durante il quale si discute il progetto svolto.

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 i"

"Automi a stati finiti deterministici
Automi a stati finiti non deterministici
Un’applicazone: ricerche testuali
Automi a stati finiti con epsilon-transizioni
"

" Espressioni regolari
Automi a stati finiti ed espressioni regolari
Applicazioni delle espressioni regolari
Proprieta’ algebriche per le espressioni regolari

"

"Proprieta’ del linguaggi regolari
Pumping Lemma per diimostraree che un linguaggio (non) e’ 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
Ambiguita’ 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

"

"Computabilita’
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
Illustrazione del progetto da svolgere"

Bibliografia consigliata

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

Metodi didattici

Lezioni, esercitazioni, laboratorio, sviluppo di un progetto individuale o in gruppo