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.
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. Cenni sui linguaggi di mark-up e di serializzazione e loro relazione con le grammatiche
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.
Materiale didattico
Libro di testo:
- J.E. Hopcroft, R. Motwani, J.D. Ullman, Automi, linguaggi e calcolabilità, Addison Wesley
Materiale fornito sulla piattaforma di e-learning
Periodo di erogazione dell'insegnamento
Primo semestre, Anno Accademico 2022-2023
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à. L'obiettivo di valutazione della prova scritta consiste nel controllo intensivo della preparazione su alcuni argomenti fondamentali del programma d’esame, e nel controllo delle competenze di problem solving disciplinare.
Durante il corso, sono previste due prove scritte in itinere. Tali prove hanno lo stesso formato e gli stessi obiettivi della prova scritta, e vertono rispettivamente sulla prima metà e sulla seconda metà del programma d'esame.
Si è ammessi al colloquio orale se è stata superata la prova scritta oppure entrambe le prove in itinere, e se sono stati consegnati gli esercizi relativi al laboratorio, così come specificato nella pagina Web del corso sulla piattaforma di eLearning (Moodle). L'obiettivo degli esercizi di laboratorio è valutare la capacità dello studente di applicare alcuni degli argomenti del corso a un problema pratico. Al colloquio orale, oltre alla discussione dello scritto, vengono fatte domande sugli argomenti del corso. L'obiettivo del colloquio orale è valutare la capacità dello studente di esporre gli argomenti del corso, e di effettuare brevi ragionamenti su di essi.
La valutazione è complessiva e viene definita al colloquio orale.
Orario di ricevimento
Su appuntamento
Sustainable Development Goals
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.
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. Basic notions on mark-up and serialization languages and their relation to grammars
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.
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
Didactic material provided on the e-learning platform
Semester
First semester, Academic Year 2022-2023
Assessment method
The assessment method consists of written and oral examination, and 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 evaluation objective of the written test consists in the intensive control of the preparation on some fundamental topics of the exam program, and in the control of disciplinary problem solving skills.
During the course, there are two written tests in progress. These tests have the same format and the same objectives as the written test, and focus respectively on the first half and the second half of the exam program.
The student is admitted to the oral exam if he/she has passed the written test or both of the ongoing tests, and if the exercises related to the laboratory have been delivered, as specified on the web page of the course on the eLearning platform (Moodle). The objective of the laboratory exercises is to evaluate the student's ability to apply some of the course topics to a practical problem. During the oral interview, in addition to the discussion of the written exam, questions are asked on the topics of the course. The objective of the oral interview is to evaluate the student's ability to present the topics of the course, and to make brief thoughts on them.
The assessment is comprehensive and is defined in the oral interview.
Office hours
On appointment
Sustainable Development Goals
Staff
-
Alessandra Agostini
-
Alberto Ottavio Leporati
-
Sara Lucia Manzoni
-
Lucia Pomello Chinaglia Pomello
