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= {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.
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
Sul sito docente sono disponibili delle dispense:
http://www.dmi.unict.it/~madonia/linguaggiFormali.html
* | Argomenti | Riferimenti testi | |
1 | * | Introduzione ai linguaggi formali | Dai testi 1) e 2) |
2 | * | Automi a stati finiti e linguaggi regolari | Dai testi 1) e 2) |
3 | * | Grammatiche e linguaggi context-free | Dai testi 1) e 2) |
4 | * | Automi a pila | Dai testi 1) e 2) |
5 | * | Macchine di Turing | Dai testi 1) e 2) |
6 | * | Automi linear-bounded e linguaggi context-sensitive | Dai testi 1) e 2) |
7 | * | Gerarchia di Chomsky | Dai testi 1) e 2) |
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.
La prima prova in itinere verterà sulla prima parte del corso (Automi a stati finiti e linguaggi regolari) e si svolgerà in una data concordata con gli studenti.
La seconda prova in itinere verterà sulla seconda parte del corso e si svolgerà in occasione del primo appello di esami.
Le prove in itinere consistono in domande aperte sugli argomenti trattati a lezione.
L’esame finale può essere completato mediante due prove in itinere.
La prova finale consiste in domande aperte sugli argomenti trattati a lezione.
http://www.dmi.unict.it/~madonia/linguaggiFormali.html