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: 
2016/2017
Anno di corso: 
2
Anno accademico di erogazione: 
2017/2018
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’applicazione: ricerche testuali
Automi a stati finiti con epsilon-transizioni"
3 " Espressioni regolari
Automi a stati finiti ed 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.