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

LINGUAGGI E COMPUTABILITA'

Scheda dell'insegnamento

Anno accademico di regolamento: 
2015/2016
Anno di corso: 
2
Anno accademico di erogazione: 
2016/2017
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 oltre allo svolgimento di alcuni esercizi svolti in laboratorio durante il 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

1 "Introduzione ai contenuti del corso
I concetti matematici di base per la teoria degli automi"

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

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

"

4 "Proprieta’ del linguaggi regolari
Pumping Lemma per diimostrare che un linguaggio (non) e’ regolare
Chiusura di linguaggi regolari rispetto ad operazioni booleane
Equivalenza e minimizzazione di automi
"

5 "Grammatiche
Grammatiche Libere dal Contesto
Alberi sintattici
Applicazioni delle Grammatiche Libere dal Contesto
Ambiguita’ nelle Grammatiche e nei Linguaggi
"

6 "Macchine di Turing
Problemi che i calcolatori non possono risolvere
La Macchina di Turing
Estensione alla Macchina di Turing semplice
Macchine di Turing ridotte

"

7 "Computabilita’
Linguaggi non Ricorsivamente Enumerabili
Linguaggi Ricorsivamente Enumerabile e Ricorsivi
Problemi indecidibili relativi alle Macchine di Turing

"

8 "Analizzatori lessicali e sintattici
Linguaggi di mark-up: XML"

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.