Linguaggi formali e automi

A.A. 2024/2025
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.
Corso singolo

Questo insegnamento può essere seguito come corso singolo.

Programma e organizzazione didattica

Edizione unica

Responsabile
Periodo
Secondo semestre

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.
Il materiale didattico è reperibile dal sito dell'insegnamento:
https://myariel.unimi.it/course/view.php?id=3175
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 dell'insegnamento. Le domande consistono in: definizioni formali, enunciati di teoremi e costruzioni/dimostrazioni. Gli esercizi verificano l'aspetto applicativo della materia mentre le domande aperte verificano la capacità di ragionamento sugli argomenti presentati a lezione. La prova d'esame ha durata di circa un'ora e mezza e il voto è espresso in trentesimi. Nella valutazione viene fortemente considerata la capacità di formalizzare i concetti. Un voto compreso tra 18 e 24 indica una conoscenza sufficiente a esporre gli argomenti mediante l'uso di un appropriato formalismo, un voto compreso tra 25 e 30 evidenzia anche la capacità di dimostrare e/o applicare enunciati di teoremi. Il voto viene comunicato direttamente allo studente tramite SIFA.
INF/01 - INFORMATICA - CFU: 6
Lezioni: 48 ore
Turni:
Turno
Docente: Palano Beatrice Santa
Docente/i
Ricevimento:
su appuntamento
Via Celoria, 18 - stanza: 4011