Linguaggi formali e automi
A.A. 2018/2019
Learning objectives
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.
Expected learning outcomes
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.
Course syllabus and organization
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.
Professor(s)