Course information | Languages and Computability

Course Syllabus

Italiano ‎(it)‎
English ‎(en)‎

Export

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.
4 esercitazioni da 3 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, settimanalmente, degli esercizi di autovalutazione.

Materiale didattico

Libro di testo:

J.E. Hopcroft, R. Motwani, J.D. Ullman, Automi, linguaggi e calcolabilità, Addison Wesley
Keith D. Cooper, Linda Torczon, Engineering a Compiler (Third Edition), Morgan Kaufmann

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.

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 dell'insegnamento.

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 termine del colloquio orale.

Orario di ricevimento

Su appuntamento

Sustainable Development Goals

ISTRUZIONE DI QUALITÁ

Export

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.

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.
4 exercises of 3 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 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
Keith D. Cooper, Linda Torczon, Engineering a Compiler (Third Edition), Morgan Kaufmann

Learning material provided on the e-learning platform

Semester

First semester

Assessment method

The assessment method consists of written and oral examination.

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 mid-term written tests. These tests have the same format and the same objectives as the written examination, and focus respectively on the first half and the second half of the course program.

The student is admitted to the oral exam if he/she has passed the written test or both of the mid-term 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 at the end of the oral interview.