- Languages and Computability
- Summary
Course Syllabus
Obiettivi
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 sintetici
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
Prerequisiti
I
contenuti degli insegnamenti del primo anno
Modalità didattica
Lezioni,
esercitazioni, laboratorio. Il corso è erogato in italiano.
Materiale didattico
Libro di testo:
- J.E. Hopcroft, R. Motwani, J.D. Ullman, Automi, linguaggi e calcolabilità, Addison Wesley
Periodo di erogazione dell'insegnamento
Primo semestre, Anno Accademico 2019-2020
Modalità di verifica del profitto e valutazione
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.
La valutazione è complessiva e viene definita al colloquio orale.
Orario di ricevimento
Su appuntamento
Aims
The
course puts in relation formal language theory with the parsing of programming languages
and aims to make the student aware of the limits of computing. The student will
be able to define regular and context-free grammars that are necessary to use
standard parsing tools and to use basic mark-up languages
Contents
Finite
automata, regular languages and regular expressions. Context-free languages,
context-free grammars and pushdown automata. Elements of the theory of
computation: Turing machine, the Church-Turing thesis, the Universal Turing machine,
unsolvable problems. Mark-up and serialization languages and their relation to
grammars
Detailed program
- Introduction and motivations. Basic mathematical concepts for automata theory
- Deterministic finite state automata. Non-deterministic finite state automata. An application: searching in texts. Finite state automata with epsilon-moves
- Regular expressions. Finite state automata and regular expressions. Applications of regular expressions. Algebraic properties of regular expressions
- Properties of regular languages. The Pumping Lemma as a tool to (dis)prove regularity of a language. Regular languages closure in respect to boolean operations. Equivalence and minimization of automata
- Grammars. Context free grammars. Parse trees. Applications of context free grammars. Ambiguity of grammars and of languages
- Turing Machines. Uncomputable problems. The basic Turing machine. Extensions of the basic Turing machine. Reduced Turing Machines
- Computability. Non Recursively Enumerable languages. Recursively Enumerable and Recursive languages. Undecidable problems and Turing Machines
- Lexical and syntactic parsers. Mark-up languages: XML
Prerequisites
The
contents of the first year's courses
Teaching form
Lectures,
recitations, laboratory. Language: Italian.
Textbook and teaching resource
Textbook (the english version is also available):
- J.E. Hopcroft, R. Motwani, J.D. Ullman, Automi, linguaggi e calcolabilità, Addison Wesley
Semester
First semester, Academic Year 2019-2020
Assessment method
Written
and oral examination, exercises during the lab.
The written exam consists of some exercises, which are similar to the ones made in class during the lectures and present on the e-learning platform, and in some open questions on the theory of computability. During the semester, two intermediate written exams will be done, that can substitute the final written exam.
The oral exam can be done if the written exam - or the two intermediate ones - has been passed, and if the exercises during the lab have been positively evaluated.
The oral exam consists of a discussion on the written exam, as well as some questions on the contents of the course.
The score is defined at the oral exam.
Office hours
On appointment
Key information
Staff
-
Alberto Ottavio Leporati
-
Lucia Pomello Chinaglia Pomello
-
Alessandra Agostini
-
Claudio Ferretti
-
Sara Lucia Manzoni
-
Andrea Campagner