Automi E Linguaggi 2025/2026

TEORIA DEI LINGUAGGI Linguaggi regolari e automi finiti deterministici e non deterministici. Espressioni regolari e loro equivalenza con gli automi finiti. Pumping lemma per i linguaggi regolari. Chiusura dei linguaggi regolari rispetto a vari operatori. TEORIA DELLA CALCOLABILITÀ Macchine di Turing (TM). Linguaggi ricorsivamente enumerabili (RE) e ricorsivi (RL). Varianti di TM. Enumeratori. Definizione di algoritmo. Tesi di Church-Turing. TM universale. Il metodo di diagonalizzazione di Cantor. Problemi non decidibili su TM: accettazione e fermata LINGUAGGI DI PROGRAMMAZIONE Nomi e ambienti: Nomi, oggetti denotabili, ambienti. "Scope rule" statica e dinamica. Gestione della memoria (statica, dinamica ("stack" "heap")). Implementazione di "scope rules" (catena statica e dinamica)). Composizione di comandi e controllo del flusso: Espressioni. Comandi. Comandi per il controllo del flusso (iterativi e condizionali). Ricorsione (ricorsione in coda). Tipi di dato e composizione dei dati: Tipi di dato scalari e composti. Equivalenza, compatibilità e conversione tra tipi di dato. Polimorfismo e "overloading". Astrazione sul controllo e sottoprogrammi: Sottoprogrammi. Passaggio di parametri. Astrazione sui dati: "Information hiding”" e tipi di dato astratti. Moduli. Paradigma orientato agli oggetti (oggetti, classi, incapsulamento, ereditarietà (singola, multipla), sottotipazione, risoluzione dinamica dei metodi, problematiche implementative (ereditarietà singola, classe base fragile)).