Sillabo dell'insegnamento

• A - Fondamenti
* ALF - Automi e Linguaggi Formali
Trasformazioni delle grammatiche libere da contesto; forma normale di Chomsky; forma normale di Greibach; automi a pila deterministici e non; equivalenza tra automi a pila e grammatiche libere da contesto; proprietà di chiusura. Linguaggi deterministici e grammatiche LR(k).

* CAL - Calcolabilita'
Calcolabilità: Macchine di Turing e funzioni Turing calcolabili. Modelli di calcolo funzionale. Funzioni iterative e ricorsive su sequenze. Universalità dei modelli di calcolo.
* CAL - Calcolabilita'
Autoriferimento: il problema della codifica dei programmi. Funzioni non calcolabili: il metodo della diagonalizzazione e il problema della fermata. Il teorema del parametro e della funzione universale. Operazioni effettive su funzioni computabili.
* CAL - Calcolabilita'
Problemi decidibili, indecidibili e semidecidibili. Il metodo della riduzione.
* CAL - Calcolabilita'
Teoremi di Rice. Insiemi ricorsivi e ricorsivamente enumerabili. Proprietà di chiusura.
* CAL - Calcolabilita'
Definizioni ricorsive. Ordinamenti parziali, funzioni monotone e punti fissi. Funzionali ricorsivi.
* CAL - Calcolabilita'
Il primo teorema di ricorsione e il secondo teorema di ricorsione.
* ALF - Automi e Linguaggi Formali
Linguaggi Formali: Linguaggio, sintassi e semantica, ambiguità, classificazione di Chomsky.
 Linguaggi sensibili al contesto e tipo 0: Grammatiche sensibili al contesto e generali; Macchina di Turing, relazione con problemi di decidibilità
* ALF - Automi e Linguaggi Formali
Linguaggi liberi da contesto e regolari: Albero di derivazione; applicazioni in compilazione. Automi finiti deterministici e non; equivalenza tra grammatiche regolari e automi finiti; proprietà di chiusura rispetto alle operazioni di composizione; espressioni regolari e loro proprietà;