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 dimostrare 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. Definizione di Macchina di Turing. Estensioni alla Macchina di Turing semplice. Macchine di Turing ridotte
- Computabilità. Linguaggi non Ricorsivamente Enumerabili. Linguaggi Ricorsivamente Enumerabili 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.
Sulla piattaforma di eLearning (Moodle) verranno resi disponibili, settimanalmente, degli esercizi di autovalutazione.
Nel periodo di emergenza Covid-19 le lezioni ed esercitazioni saranno videoregistrate; ci saranno inoltre dei momenti sincroni (in streaming, non registrati) di discussione e risposta alle domande degli studenti, su argomenti prestabiliti. I laboratori si svolgeranno in modalità virtuale, secondo le indicazioni date dall'Ateneo.
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 2021-2022
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à.
Si è ammessi al colloquio orale se è stata superata la prova scritta 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, vengono fatte domande sugli argomenti del corso.
La valutazione è complessiva e viene definita al colloquio orale.
Nel periodo di emergenza Covid-19 gli esami orali si svolgeranno in videoconferenza, utilizzando la piattaforma Cisco WebEx o Google Meet. Lo scritto verrà sostituito da alcuni esercizi svolti durante l'esame 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.
Some self-assessment exercises will be weekly published on the eLearning (Moodle) web page.
During the Covid-19 emergency, lectures and recitations will be recorded and online. There will be some previously planned discussions and answers to questions in streaming and not recorded . Laboratory will be virtual, according to the indications given by our University.
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 2021-2022
Assessment method
Written and oral examination, exercises performed 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.
The oral exam can be done if the written exam has been passed, and if the exercises made 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.
During the Covid-19 emergency, the oral exams will be online either on Cisco WebEx or on Google Meet. The written exam will be substituted by some exercises performed during the oral exam.
Office hours
On appointment
Staff
-
Alessandra Agostini
-
Alberto Ottavio Leporati
-
Sara Lucia Manzoni
-
Lucia Pomello Chinaglia Pomello
-
Federica Adobbati
-
Martina Saletta