Linguaggi formali e automi
A.A. 2018/2019
Obiettivi formativi
Nel corso si espongono in modo concettuale problematiche classiche (analisi e sintesi) relative a Sistemi e Modelli, abituando lo studente all'uso di metodi formali.
Risultati apprendimento attesi
Non definiti
Periodo: Secondo semestre
Modalità di valutazione: Esame
Giudizio di valutazione: voto verbalizzato in trentesimi
Corso singolo
Questo insegnamento non può essere seguito come corso singolo. Puoi trovare gli insegnamenti disponibili consultando il catalogo corsi singoli.
Programma e organizzazione didattica
Linea Milano
Responsabile
Periodo
Secondo semestre
STUDENTI FREQUENTANTI
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.
Informazioni sul programma
Sul sito del corso è disponibile il programma suddiviso lezione per lezione
Propedeuticità
nessuna
Prerequisiti
Nessun prerequisito particolare.
La prova d'esame consiste di uno scritto di circa cinque 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, espressa in trentesimi, viene fortemente considerata la capacità di formalizzare i concetti.
La prova d'esame consiste di uno scritto di circa cinque 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, espressa in trentesimi, viene fortemente considerata la capacità di formalizzare i concetti.
Metodi didattici
Corso tradizionale: il corso si compone di lezioni frontali rivolte alla spiegazione della teoria e allo svolgimento di esercizi.
Materiale di riferimento
STUDENTI NON FREQUENTANTI
-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.
- Bertoni, Palano. Linguaggi Formali e Automi. Dispense reperibili dal sito del corso.
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.
La prova d'esame consiste di uno scritto di circa cinque 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, espressa in trentesimi, viene fortemente considerata la capacità di formalizzare i concetti.
La prova d'esame consiste di uno scritto di circa cinque 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, espressa in trentesimi, viene fortemente considerata la capacità di formalizzare i concetti.
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.
- Bertoni, Palano. Linguaggi Formali e Automi. Dispense reperibili dal sito del corso.
Docente/i