Syllabus del corso
Obiettivi
Conoscenza e capacità di comprensione
Gli studenti apprenderanno gli elementi della teoria dei linguaggi formali e le sue relazioni con l'analisi lessicale e sintattica, incluse quelle rilevanti nei linguaggi di programmazione.
Conoscenza e capacità di comprensione applicate
Gli studenti saranno in grado di definire grammatiche regolari e libere dal contesto che sono necessarie per l’utilizzo di analizzatori lessicali e sintattici. Inoltre acquisiranno la capacità di utilizzare analizzatori in contesti pratici.
Autonomia di giudizio
Gli studenti acquisiranno la capacità di valutare quale grammatica utilizzare per descrivere diversi linguaggi.
Abilità comunicative
La grande attenzione posta sugli aspetti formali permetterà agli studenti di comprendere l’importanza di una comunicazione non ambigua, utilizzando la terminologia corretta per esprimere le nozioni e i concetti appresi.
Capacità di apprendere
La formalizzazione dei concetti faciliterà i meccanismi di apprendimento deduttivo. Inoltre, l'esposizione di esempi ed esercizi svolti alla lavagna, subito dopo aver spiegato una tecnica o un algoritmo, consentirà di chiarire eventuali dubbi e casi particolari.
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. Analizzatori lessicali e sintattici.
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. Pumping Lemma per Grammatiche Libere dal Contesto
- Macchine di Turing. Problemi che i computer non possono risolvere. Definizione di Macchina di Turing. Estensioni alla Macchina di Turing. 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. Algoritmi di Parsing.
Prerequisiti
I contenuti degli insegnamenti del primo anno
Modalità didattica
28 lezioni da 2 ore svolte in aula, in modalità erogativa, in presenza.
12 ore svolte in laboratorio, in modalità erogativa nella parte iniziale che è volta a coinvolgere gli studenti in modo interattivo nella parte successiva. Tutte le attività sono svolte in presenza.
Il corso è erogato in italiano.
Sulla piattaforma di eLearning (Moodle) verranno resi disponibili alcuni esercizi di autovalutazione.
Materiale didattico
Libro di testo:
- J.E. Hopcroft, R. Motwani, J.D. Ullman, Automi, linguaggi e calcolabilità, Addison Wesley
- Dick Grune e Ceriel JH Jacobs. Parsing techniques. Monographs in Computer Science. Springer
Materiale fornito sulla piattaforma di e-learning
Periodo di erogazione dell'insegnamento
Primo semestre
Modalità di verifica del profitto e valutazione
La verifica dell'apprendimento comprende una prova scritta e un colloquio orale.
La valutazione è complessiva e viene definita al termine del colloquio orale.
La prova scritta richiede di svolgere 6 esercizi simili a quelli svolti a lezione e presenti sul sito e-learning del corso. L'obiettivo di valutazione della prova scritta consiste nel controllo intensivo della preparazione su alcuni argomenti fondamentali del programma dell'insegnamento, e nel controllo delle competenze di problem solving disciplinare.
Si è ammessi al colloquio orale se è stata superata la prova scritta.
Il colloquio orale prevede una discussione dello scritto e domande sugli argomenti del corso. L'obiettivo del colloquio orale è valutare la capacità dello studente di esporre gli argomenti del corso utilizzando il giusto livello di formalismo, e di effettuare brevi, ma corretti, ragionamenti su di essi.
L'orale verte su tutti i contenuti del corso, inclusi gli argomenti trattati in laboratorio.
L'orale deve essere sostenuto nello stesso appello in cui si è superato lo scritto. Non è possibile sostenere l'orale se non si è superato lo scritto.
Chi non supera l'orale deve rifare lo scritto.
Gli appelli sono a Novembre, Gennaio, Febbraio, Giugno, Luglio, e Settembre. Gli studenti del secondo anno possono svolgere l’appello completo a partire da Gennaio.
Durante il corso sono previste due prove scritte in itinere, erogate a Novembre e a Gennaio. 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 dell'insegnamento.
Il superamento di ciascuna prova in itinere permette di non svolgere i corrispondenti esercizi della prova scritta.
Nell’appello di Febbraio è possibile svolgere la prova scritta completa oppure recuperare una delle due prove parziali, svolgendo i tre esercizi corrispondenti. E’ possibile rifare una delle due prove parziali anche se la si è precedentemente superata. In questo caso, il nuovo voto annulla il voto precedente.
Analogamente, è possibile svolgere la prova scritta completa anche se si è precedentemente superata una delle due prove parziali, annullandone il voto.
Chi supera le due prove in itinere a Novembre e a Gennaio, può scegliere di sostenere la prova orale nell’appello di Gennaio o di Febbraio.
Orario di ricevimento
Su appuntamento
Sustainable Development Goals
Aims
Knowledge and Understanding
Students will learn the fundamentals of formal language theory and its connections to lexical and syntactic analysis, including those relevant to programming languages.
Applied Knowledge and Understanding
Students will be able to define regular and context-free grammars necessary for the use of lexical and syntactic analyzers. They will also acquire the ability to use analyzers in practical contexts.
Independent Judgment
Students will develop the ability to evaluate which grammar is most appropriate for describing different languages.
Communication Skills
The great attention paid to formal aspects will allow students to understand the importance of unambiguous communication, using the correct terminology to express the notions and concepts learned.
Learning Skills
The formalization of concepts will facilitate deductive learning mechanisms. Furthermore, presenting examples and exercises on the board, immediately after explaining a technique or algorithm, helps clarify any doubts and particular cases.
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. Lexical analyzers and parsers.
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. Pumping Lemma for context free grammars
- 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. Parsing algorithms
Prerequisites
The contents of the first year's courses
Teaching form
28 lessons of 2 hours held in the classroom, in delivery mode, in person.
12 hours held in the laboratory, in delivery mode in the initial part which is aimed at involving students in an interactive way in the subsequent part. All activities are held in person.
The course is delivered in Italian.
Some self-assessment exercises will be 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
- Dick Grune e Ceriel JH Jacobs. Parsing techniques. Monographs in Computer Science. Springer
Learning material provided on the e-learning platform
Semester
First semester
Assessment method
The learning assessment includes a written exam and an oral exam.
The grade is overall and is determined at the end of the oral exam.
The written exam requires completing six exercises similar to those covered in class and available on the course e-learning site. The objective of the written exam is to intensively test students' preparation on key topics from the course program and to assess their problem-solving skills.
Students who pass the written exam are admitted to the oral exam.
The oral exam includes a discussion of the written exam and questions on course topics. The objective of the oral exam is to assess the student's ability to present the course topics using the appropriate level of formalism and to make brief, yet correct, arguments about them.
The oral exam covers all course content, including the topics covered in the lab.
The oral exam must be taken in the same exam session in which the written exam was passed. Students who have not passed the written exam cannot take the oral exam.
Anyone who fails the oral exam must retake the written exam.
The exam sessions are in November, January, February, June, July, and September. Second-year students can take the full exam starting in January.
During the course, there are two ongoing written tests, held in November and January. These tests have the same format and objectives as the written exam, and cover the first and second halves of the course syllabus, respectively.
Passing each ongoing test allows students to skip the corresponding written exam exercises.
In the February exam session, students can take either the full written exam or one of the two partial exams by completing the three corresponding exercises. Students can retake one of the two partial exams even if they have previously passed it. In this case, the new grade cancels the previous grade.
Similarly, students can take the full written exam even if they have previously passed one of the two partial exams, canceling the previous grade.
Those who pass the two ongoing tests in November and January can choose to take the oral exam in the January or February session.
Office hours
By appointment
Sustainable Development Goals
Staff
-
Luca Bernardinello
-
Gianluca Della Vedova
-
Alberto Ottavio Leporati
