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.

La frequenza delle lezioni non è obbligatoria ma, per una piena comprensione degli argomenti del corso, è fortemente consigliata.

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.

Proprieta’ di chiusura della classe dei linguaggi AF-regolari.

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.

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.

Applicazioni.

Automi linear-bounded e linguaggi context-sensitive:

Definizioni ed esempi

Equivalenza tra automi linear-bounded e grammatiche context-sensitive.

Gerarchia di Chomsky

Libro di testo:

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

Per una trattazione più approfondita e un’inquadramento più generale dei vari argomenti si consiglia di consultare anche:

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

Esame scritto e colloquio orale.

Durante il corso sono previste alcune prove in itinere.

È possibile concordare col docente la data e l'orario per lo svolgimento delle prove d'esame.

http://www.dmi.unict.it/~madonia/linguaggiFormali.html