Il corso, di carattere teorico, ha come obiettivo l'acquisizione da parte dello studente delle nozioni basilari relative alla teoria degli automi e dei linguaggi formali compresi i principali risultati limitativi nell'ambito della teoria della calcolabilità. Tali conoscenze sono rivolte a formare e ad aumentare le capacità di astrazione attraverso la rappresentazione simbolica e di comprensione di un linguaggio scientifico astratto e simbolico, capacità che hanno un ruolo fondamentale in vari ambiti dell'informatica come, ad esempio, nello sviluppo dei compilatori, nella modellazione di sistemi complessi e nell'ingegneria del software.
Al termine del corso lo studente sarà in grado di. (1) descrivere i principali modelli computazionali (automi a stati finiti, automi a pila, macchine di Turing), le loro caratteristiche e la loro potenza computazionale in termini di linguaggi riconosciuti; (2) definire formalmente la nozione di computazione nei vari modelli studiati; (3) identificare il ruolo dei vari linguaggi (in particolare per i linguaggi regolari e context-free) nel processo di compilazione dei linguaggi di programmazione e in altre applicazioni di base dei linguaggi; (4) identificare e utilizzare le notazioni (generatori) per la descrizione dei linguaggi regolari e i linguaggi context-free; (5) applicare in modo appropriato riconoscitori e generatori allo studio di semplici linguaggi; (6) dimostrare un’appropriata comprensione dei limiti dei vari modelli computazionali; (7) riconoscere e utilizzare la terminologia propria della teoria degli automi, dei linguaggi formali e della teoria della computabilità.
Prerequisiti
Per un proficuo apprendimento di questo insegnamento lo studente deve padroneggiare le nozioni matematiche e le tecniche dimostrative impartite nell’insegnamento fondamentale di Algebra e Geometria del primo anno, che dunque costituisce propedeuticità obbligatoria. Inoltre, è consigliabile che lo studente abbia frequentato e sostenuto gli insegnamenti fondamentali di Programmazione e Algoritmi e Strutture Dati del primo anno di corso.
