LINGUAGGI FORMALI

1. Conoscenza e capacità di comprensione (knowledge and understanding): il corso ha come obiettivo principale l'acquisizione da parte dello studente di conoscenze avanzate di teoria dei linguaggi formali, relativamente anche a possibili applicazioni. Si noti che gli studi in tale ambito consentiranno allo studente di comprendere meglio nozioni, risultati e concetti fondamentali per un informatico.
2. Capacità di applicare conoscenza e comprensione (applying knowledge and understanding): lo studente svilupperà le sue capacità di formalizzazione ed astrazione e acquisirà le competenze necessarie per affrontare in modo chiaro e rigoroso numerosi problemi di carattere applicativo. Tali problemi spaziano dal riconoscimento di linguaggi artificiali e naturali, al pattern matching di stringhe (con applicazioni importanti alla bioinformatica), alla teoria dei giochi.
3. Autonomia di giudizio (making judgements): lo studente sarà in grado di utilizzare gli strumenti formali più opportuni in diversi contesti applicativi, motivandone adeguatamente la scelta ed elaborando autonomamente proprie soluzioni.
4. Abilità comunicative (communication skills): lo studente acquisirà ulteriori abilità comunicative e una maggiore padronanza degli strumenti espressivi e argomentativi del ragionamento formale.
5. Capacità di apprendimento (learning skills): il corso si propone, come obiettivo, di fornire allo studente le necessarie metodologie, soprattutto teoriche, per poter affrontare e risolvere autonomamente nuove problematiche che dovessero sorgere durante l'attività progettuale tipica di un Laureato Magistrale.

Nozioni di base di Logica e Matematica discreta.

Per una piena comprensione degli argomenti del corso la frequenza delle lezioni è fortemente consigliata.

DESCRIZIONE GENERALE SINTETICA

Il corso affronta tematiche avanzate nell'ambito della teoria dei linguaggi formali e delle possibili applicazioni. In particolare, alla presentazione teorica dei linguaggi formali e dei metodi per riconoscerli, generarli ed elaborarli, sarà affiancata la presentazione di problemi di carattere applicativo ad essi collegati. Particolare attenzione sarà rivolta allo studio degli automi a stati finiti, visti come descrizione matematica di un sistema discreto sequenziale, agli automi a pila e alle Macchine di Turing, viste come modello generale di computazione.

PROGRAMMA PARTICOLAREGGIATO

Introduzione ai linguaggi formali: Grammatiche e riconoscitori.

Automi a stati finiti e linguaggi regolari: Automi a stati finiti: deterministici, non deterministici, con epsilon-transizioni. Equivalenza fra Automi a stati finiti con epsilon-transizioni e Automi a stati finiti senza epsilon-transizioni. La classe dei linguaggi AF-regolari e proprieta’ di chiusura. Espressioni regolari e linguaggi regolari. Ogni linguaggio regolare e’ AF-regolare. Teorema di Kleene. Pumping lemma per linguaggi regolari (solo enunciato). Applicazioni del Pumping Lemma: algoritmi di decidibilità per linguaggi regolari. Teorema di Myhill-Nerode. Minimizzazione di automi a stati finiti. Applicazioni.

Grammatiche context-free: Alberi di derivazione. Semplificazione di grammatiche context-free: eliminazione dei simboli inutili; eliminazione delle epsilon-produzioni; eliminazione delle produzioni unitarie. Forma normale di Chomsky:trasformazione di una grammatica context-free in un equivalente in CNF. Forma normale di Greibach (solo la definizione). Grammatiche ambigue, non-ambigue e inerentemente ambigue. Pumping Lemma per linguaggi context-free. Applicazioni del Pumping Lemma per linguaggi context-free. Lemma di Ogden (solo enunciato). Il linguaggio L= {aⁱb^jc^k | i ≠ j, j ≠ k , i ≠ k} non e’ context-free. Problema dell’appartenenza per linguaggi context-free. Applicazioni.

Automi a pila: Linguaggio accettato per stack vuoto e per stati finali. Equivalenza dei due metodi di accettazione. Automi a pila deterministici. Equivalenza tra automi a pila e grammatiche context-free (cenni). Applicazioni.

Macchine di Turing: Linguaggi ricorsivamente enumerabili. Equivalenza fra macchine di Turing deterministiche e non deterministiche. Equivalenza fra macchine di Turing e grammatiche senza restrizioni (cenni) . Applicazioni.

Automi linear-bounded e linguaggi context-sensitive: Definizioni ed esempi. Equivalenza tra automi linear-bounded e grammatiche context-sensitive (cenni).

Gerarchia di Chomsky.

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Automi, linguaggi e calcolabilità , Pearson Paravia Bruno Mondadori S.p.A. Terza Edizione, Marzo 2009.

John E. Hopcroft, Jeffrey D. Ullman. Introduction to automata theory, languages and computation, Addison-Wesley.

Esame scritto e colloquio orale.