- Oggetto:
- Oggetto:
Calcolabilità e complessità con elementi di linguaggi formali e traduttori
- Oggetto:
Computability and Complexity with Elements of Formal Languages and Compilers
- Oggetto:
Anno accademico 2025/2026
- Codice attività didattica
- MAT0326
- Docente
- Gian Luca Pozzato (Titolare)
- Corso di studio
- Laurea in Matematica
- Anno
- 3° anno
- Periodo
- Primo semestre
- Tipologia
- D.M. 270 TAF C - Affine o integrativo
- Crediti/Valenza
- 9
- SSD attività didattica
- INFO-01/A - Informatica
- Erogazione
- Tradizionale
- Lingua
- Italiano
- Frequenza
- Facoltativa
- Tipologia esame
- Scritto
- Oggetto:
Sommario insegnamento
- Oggetto:
Avvisi
- Oggetto:
Obiettivi formativi
L'insegnamento ha l'obiettivo di fornire le nozioni fondamentali relative alla specifica di linguaggi formali. I concetti, i formalismi, le metodologie e le tecniche presentate trovano applicazione in un'ampia gamma di contesti in cui si richiede la specifica e la comprensione di informazioni strutturate. La padronanza dei concetti e degli strumenti riguardanti i linguaggi formali rientra fra gli Obiettivi formativi dell'area informatica di base del CdS in Matematica.
The course aims to provide students with fundamental notions related to the specification of formal languages. The presented concepts, formalisms, methodologies and techniques are applicable in a wide variety of contexts in which the specification and understanding of structured data are necessary. Obtaining skills regarding the concepts and tools regarding formal languages and translators forms part of the "Obiettivi formativi specifici del CdS in Matematica".
- Oggetto:
Risultati dell'apprendimento attesi
Comprensione e acquisizione della terminologia tecnica del settore. Conoscenza delle metodologie fondamentali per la descrizione della sintassi di linguaggi formali.
CONOSCENZA E CAPACITÀ DI COMPRENSIONE. Acquisizione di conoscenze teoriche e applicative relative a linguaggi formali.
CAPACITÀ DI APPLICARE CONOSCENZA E COMPRENSIONE. Acquisizione dell’abilità di applicare conoscenza teorica di linguaggi formali alla soluzione di problemi pratici.
AUTONOMIA DI GIUDIZIO. Acquisizione delle capacità per la valutazione delle correttezza della progettazione di analizzatori sintattici per linguaggi formali e per valutare l’efficacia del loro funzionamento.
ABILITÀ COMUNICATIVE. Acquisizione della capacità di utilizzare framework precisi per ragionare di linguaggi formali (automi a stati finiti, grammatiche).
CAPACITÀ DI APPRENDIMENTO. Acquisizione di capacità di imparare e autovalutarsi, sia rispetto a problemi teorici sia rispetto a problemi pratici, in un modo autonomo.
Understanding and acquisition of the technical terminology of the field. Knowledge and mastery of the basic methodologies for formal languages.
KNOWLEDGE AND UNDERSTANDING Acquisition of theoretical and applicative skills concerning formal languages.
APPLYING KNOWLEDGE AND UNDERSTANDING Acquisition of the ability to apply theoretical knowledge of formal languages to the solution of practical problems.
MAKING JUDGEMENTS Acquisition of skills for assessing the correctness of designs for syntax analysis of formal languages, and for judging the effectiveness of their implementation and operation.
COMMUNICATION SKILLS Acquisition of the ability to use precise, unambiguous frameworks for reasoning about formal languages (finite-state automata, grammars).
LEARNING SKILLS Acquisition of the ability to learn and carry out self-assessment, with regard to both theoretical and practical problems, in an autonomous manner.
- Oggetto:
Programma
- Nozioni di base di linguaggi formali
- Automi a stati finiti
- Espressioni regolari
- Proprietà dei linguaggi regolari
- Grammatiche libere
- Automi a pila
- Proprietà dei linguaggi liberi
- Basic notions of formal languages
- Finite-state automata
- Regular expressions
- Properties of regular languages
- Context-free grammars
- Pushdown automata
- Properties of context-free languages
- Oggetto:
Modalità di insegnamento
L’insegnamento consiste in un ciclo di lezioni erogate con l'ausilio di slide, note, lavagne (fisiche o virtuali). Le lezioni sono accompagnate da sessioni interattive dedicate a chiarimenti, esempi ed approfondimenti sui contenuti del corso.
The course consists of a series of lessons supported by the use of slides, notes, blackboards (physical or virtual). The lessons will be accompanied by interactive sessions dedicated to the presentation of examples, and to the clarification and further exploration of the course contents.
- Oggetto:
Modalità di verifica dell'apprendimento
Prova scritta composta di domande di natura teorica ed esercizi su tutto il programma del corso.
Written test, composed of questions of a theoretical nature and exercises on the entire programme of the course.
Testi consigliati e bibliografia
- Oggetto:
- Libro
- Titolo:
- Introduction to the theory of Computation
- Anno pubblicazione:
- 2013
- Editore:
- Pearson
- Autore:
- M. Sipser
- ISBN
- Capitoli:
- 1,2
- Note testo:
- adottato anche per la parte di Calcolabilità e Complessità (capitoli 3,4,5,7)
- Obbligatorio:
- No
- Oggetto:
Note
3 cfu-24 ore (modulo di LINGUAGGI FORMALI E TRADUTTORI) sono appositamente erogate per il cdl in matematica , invece i restanti 6 cfu-48 ore sono mutuati da INF0090 Calcolabilità e Complessità del Corso di Laurea in Informatica.
- Oggetto:
