Linguaggi formali e automi

A.A. 2021/2022
6
Crediti massimi
48
Ore totali
SSD
INF/01
Lingua
Italiano
Obiettivi formativi
L'insegnamento si prefigge il compito di presentare i concetti della teoria dei linguaggi formali e degli automi centrali in svariati ambiti del contesto informatico attuale, abituando lo studente all'uso di metodi formali.
Risultati apprendimento attesi
Lo studente dovrà possedere le nozioni basilari sulla questione della calcolabilità. Dovrà essere in grado di distinguere i diversi tipi di grammatiche formali ponendole in relazione con i diversi modelli di calcolo che vengono introdotti. Dovrà essere in grado di progettare automi a pila o a stati finiti per semplici linguaggi formali, minimizzare automi a stati finiti e dare espressioni regolari equivalenti.
Programma e organizzazione didattica

Edizione unica

Responsabile
Periodo
Secondo semestre
Metodi didattici:
Verranno svolte lezioni sincrone (videolezioni) utilizzando la piattaforma Zoom con registrazione completa. Verranno poi rese disponibili le lezioni per consentirne la fruizione in modalità asincrona per gli studenti non presenti in aula.

Il programma e il materiale di riferimento compresa la modalità di verifica dell'apprendimento non subiranno variazioni.
Programma
Nozioni di base.
Monoidi di parole, linguaggi, operazioni tra linguaggi, riconoscitori e generatori di linguaggi. Grammatiche e derivazioni. Grammatiche regolari, libere da contesto, dipendenti da contesto e relative classi di linguaggi.
Linguaggi regolari.
Automi a stati finiti deterministici e non deterministici. Grammatiche regolari e automi a stati finiti. Espressioni regolari. Teorema di Kleene. Congruenze sintattiche e costruzione degli automi minimi. Applicazioni: le espressioni regolari in Unix.
Linguaggi liberi da contesto.
Alberi di derivazione. Grammatiche e linguaggi ambigui. Forma normale di Chomsky. Lemma di iterazione per i linguaggi liberi da contesto. Forma normale di Greibach. Automi a pila. Caratterizzazione dei linguaggi liberi da contesto mediante gli automi a pila. Applicazioni: XML.
Prerequisiti
Nessun prerequisito particolare.
Metodi didattici
L'insegnamento si compone di lezioni frontali rivolte alla spiegazione della teoria e allo svolgimento di esercizi. La frequenza alle lezioni è fortemente consigliata.
Materiale di riferimento
-J.E. Hopcroft, J.D. Ullman. Introduction to automata theory, languages and computation.Addison-Wesley, 1979.
- Bertoni, Palano. Linguaggi Formali e Automi. Dispense reperibili dal sito del corso.
Modalità di verifica dell’apprendimento e criteri di valutazione
La prova d'esame consiste di uno scritto di circa tre domande/esercizi che coprono gli argomenti del corso. Le domande consistono in: definizioni formali, enunciati di teoremi e costruzioni/dimostrazioni. Gli esercizi verificano la comprensione della materia e la capacità di applicare i teoremi. Nella valutazione viene fortemente considerata la capacità di formalizzare i concetti.
La prova d'esame ha durata di circa un'ora e il voto, espresso in trentesimi, viene comunicato direttamente allo studente tramite SIFA.
INF/01 - INFORMATICA - CFU: 6
Lezioni: 48 ore
Docente/i
Ricevimento:
su appuntamento
Via Celoria, 18 - stanza: 4011