Sillabo dell'insegnamento

• A - Fondamenti
* ALF - Automi e Linguaggi Formali
Equivalenza tra grammatiche CF e automi a pila (PDA). Esempio delle espressioni in forma polacca. Lemma d'iterazione per i linguaggi CF. Esempi di linguaggi che non sono generati da grammatiche CF. Propriet? di chiusura per la famiglia dei linguaggi CF. Problemi de decisione per i linguaggi CF. Cenni sull'analisi sintattica.
* ALF - Automi e Linguaggi Formali
Sistemi di riscrittura. Grammatiche. Linguaggi generati da grammatiche. La gerarchia di Chomsky e sue relazioni con la classificazione degli automi. Equivalenza tra grammatiche (generali) e macchine di Turing. Equivalenza tra Grammatiche Lineari Destre (o Lineari Sinistre) e FSA.
* ALF - Automi e Linguaggi Formali
Funzioni calcolabili e problemi decidibili. Esistenza di problemi indecidibili. Linguaggi riconosciuti da macchine di Turing. Generalizzazioni e restrizioni della macchina di Turing. Linguaggi riconosciuti dai diversi modelli di automi.
* CAL - Calcolabilita'
Metodi di codifica ricorsivi primitivi. Numeri di Godel. Il linguaggio di programmazione S di Davis/Weyuker. Calcolabilità in S delle funzioni r.p. Il teorema della "fermata". Esistenza di programmi "universali". Insiemi ricorsivamente enumerabili (r.e.) e di insiemi ricorsivi.
* ALF - Automi e Linguaggi Formali
Automi a Stati Finiti (FSA) e linguaggi riconosciuti da FSA. Rappresentazione di un FSA col grafo degli stati. Lemma d'iterazione. Esempi di linguaggi non riconosciuti da FSA. Automi Finiti Deterministici (DFA) e Nondeterministici (NFA). Equivalenza tra NFA e DFA. Subset Construction. Applicazioni: algoritmi di string-matching. FSA con epsilon-transizioni.
* ALF - Automi e Linguaggi Formali
Teorema di Kleene. Algoritmi per convertire un'espressione regolare in un DFA e viceversa. FSA bidirezionali (2-FSA).Equivalenza tra 2-DFA e 1-DFA (Teorema di Rabin-Shepherdson). Problemi di decisione per i linguaggi riconosciuti da FSA. Equivalenza e minimizzazione di FSA.
* ALF - Automi e Linguaggi Formali
Proprietà di chiusura della famiglia dei linguaggi riconosciuti da FSA. Linguaggi ed Espressioni Regolari. Grammatiche Noncontestuali, o Context-Free (CF). Linguaggi generati da grammatiche CF. Albero Sintattico (o di Derivazione). Ambiguità nelle grammatiche e nei linguaggi CF. Forme Normali di Chomsky e di Greibach.
* CAL - Calcolabilita'
Nozione di calcolabilità. Enunciato e discussione della tesi di Church-Turing. Primi esempi di funzioni Turing-calcolabili.
COM - Complessita'
Le classi P ed NP. Cenni a problemi NP-completi.