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= {aibjck | 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.
Le risorse principali messe a disposizione dello studente sono le lezioni frontali, la cui frequenza, come già sottolineato, è fortemente consigliata.
Si veda anche il sito: http://www.dmi.unict.it/~madonia/linguaggiFormali.html
Esame scritto e colloquio orale.