Sillabo dell'insegnamento

• A - Fondamenti
* ALF - Automi e Linguaggi Formali
Automi a stati finiti, linguaggi regolari, espressioni regolari
* ALF - Automi e Linguaggi Formali
Automi a pila, pumping lemma
* ALF - Automi e Linguaggi Formali
Grammatiche context-free e context-sensitive, gerarchia di Chomsky
* CAL - Calcolabilita'
Macchine di Turing, computazione, accettazione, riconoscimento, esempi
* CAL - Calcolabilita'
Varianti delle Macchine di Turing: multinastro, multistack, contatori
* CAL - Calcolabilita'
Linguaggi ricorsivi e ricorsivamente enumerabili, linguaggio di diagonalizzazione
* CAL - Calcolabilita'
Funzioni calcolabili; Tesi di Church.
* CAL - Calcolabilita'
Riducibilita' tra problemi, funzione e TM universale, Halting problem
* CAL - Calcolabilita'
Proprieta' di chiusura di R ed RE, Teorema di Rice.