Linguaggi formali e automi
A.A. 2023/2024
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.
Periodo: Secondo semestre
Modalità di valutazione: Esame
Giudizio di valutazione: voto verbalizzato in trentesimi
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.
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://bpalanolfa.ariel.ctu.unimi.it/v5/home/Default.aspx
- Bertoni, Palano. Linguaggi Formali e Automi. Dispense.
Il materiale didattico è reperibile dal sito dell'insegnamento:
https://bpalanolfa.ariel.ctu.unimi.it/v5/home/Default.aspx
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.
Siti didattici
Docente/i