Sillabo dell'insegnamento

• A - Fondamenti
* ALF - Automi e Linguaggi Formali
+ AL-BACC - Basic Automata, Computability and Complexity
Automi a Stati Finiti Motivazioni, applicazioni e descrizione informale. I concetti centrali della teoria degli automi. Definizione di automa a stati finiti deterministico (DFA). Automi riconoscitori. Rappresentazione di un DFA con grafo degli stati e tabella delle transizioni. Automi a stati fini non deterministici (NFA). Teorema di equivalenza tra DFA e NFA. La ?subset construction?. Discussione sulla ?state complexity? di DFA e NFA. Applicazioni alle ricerche testuali. Automi con ε-transizioni. Eliminazione delle ε-transizioni.
* ALF - Automi e Linguaggi Formali
+ AL-BACC - Basic Automata, Computability and Complexity
Espressioni regolari. Linguaggi regolari. Applicazioni di espressioni regolari. Equivalenza tra linguaggi regolari e linguaggi riconosciuti da DFA (Teorema di Kleene). Algoritmo di eliminazione degli stati per convertire un automa in un'espressione regolare. Algoritmo di Berry e Sethi per convertire un'espressione in un automa.
* ALF - Automi e Linguaggi Formali
+ AL-BACC - Basic Automata, Computability and Complexity
Chiusura dei linguaggi regolari rispetto alle operazioni booleane e reverse. Il ?pumping lemma? per i linguaggi regolari. Applicazioni del pumping lemma. Problema di decisione se un linguaggio regolare è vuoto. Problema di inclusione dei linguaggi regolari.
* ALF - Automi e Linguaggi Formali
+ AL-BACC - Basic Automata, Computability and Complexity
Equivalenza tra automi. Problema di decisione dell'equivalenza di due DFA. Minimizzazione di automi deterministici tramite gli algoritmi classici di minimizzazione. La relazione di indistinguibilità degli stati. Automa ridotto.
* ALF - Automi e Linguaggi Formali
+ AL-BACC - Basic Automata, Computability and Complexity
Equivalenza tra automa ridotto e automa minimale. Teorema di Myhil-Nerode. Unicità dell'automa deterministico minimale.
* ALF - Automi e Linguaggi Formali
+ AL-BACC - Basic Automata, Computability and Complexity
Grammatiche e Linguaggi Liberi dal Contesto (CF) Motivazioni e descrizione informale. Definizione di grammatica. Derivazioni delle grammatiche. Linguaggio generato da una grammatica. La gerarchia di Chomsky. Le grammatiche e i linguaggi CF.
* ALF - Automi e Linguaggi Formali
+ AL-BACC - Basic Automata, Computability and Complexity
Alberi sintattici. Ambiguità nelle grammatiche e nei linguaggi CF: grammatiche ambigue, eliminazione delle ambiguità, ambiguità inerente. Alcune applicazioni delle grammatiche libere dal contesto. Forme normali. Forma normale di Chomsky. Pumping lemma per i linguaggi CF.
* ALF - Automi e Linguaggi Formali
+ AL-BACC - Basic Automata, Computability and Complexity
Applicazioni del pumping lemma. Proprietà di chiusura dei linguaggi CF. Problemi di decisione per i linguaggi CF
* CAL - Calcolabilità
+ AL-BACC - Basic Automata, Computability and Complexity
Breve introduzione alla teoria della calcolabilità. La macchina di Turing. Funzioni calcolate da una macchina di Turing. Linguaggi riconosciuti da una macchina di Turing. La tesi di Turing-Church. La macchina universale di Turing. Esistenza di funzioni non calcolabili. Il problema della "fermata" di una macchina di Turing. Problemi decidibili e indecidibili. Problemi intrattabili. Modelli particolari di macchine di Turing. Gerarchia di Chomsky e decidibilità.