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