Sillabo dell'insegnamento

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