- 6 marzo 2013 - Lezione 1
Introduzione. Generalità su linguaggi, linguaggi formali, macchine e automi. Alcuni esempi informali di automi a stati finiti. Nozioni base su alfabeti, stringhe, linguaggi. Il problema della rappresentazione finita di linguaggi. Il linguaggio delle parentesi bilanciate: definizione riconoscitiva e definizione generativa. - 13 marzo 2013 - Lezione 2
Automi a stati finiti deterministici: definizione, funzione di transizione estesa alle stringhe, linguaggio accettato. Rappresentazione mediante tabelle e mediante diagrammi di transizione. Esempi.
Automi a stati finiti nondeterministici: definizione, funzione di transizione estesa alle stringhe, linguaggio accettato. Esempi. - 20 marzo 2013 - Lezione 3
Trasformazione di automi nondeterministici in automi deterministici: la costruzione per sottoinsiemi. Equivalenza tra automi a stati finiti deterministici e nondeterministici. Automi con epsilon-mosse. - 27 marzo 2013 - Lezione 4
Trasformazione di automi con epsilon-mosse in automi nondeterministici e deterministici.
Operazioni su linguaggi: operazioni insiemistiche (unione, intersezione, complemento, differenza), prodotto o concatenazione, potenza, chiusura di Kleene, chiusura positiva. Le espressioni regolari. Esempi. - 10 aprile 2013 - Lezione 5
La classe dei linguaggi regolari. Il teorema di Kleene: dalle espressioni regolari agli automi a stati finiti; dagli automi a stati finiti alle espressioni regolari. - 17 aprile 2013 - Lezione 6
Il pumping lemma per i linguaggi regolari. Esempi di dimostrazioni di non regolarità mediante il pumping lemma. Chiusura della classe dei linguaggi regolari rispetto alle operazioni booleane. Problemi di decisione per linguaggi regolari: come decidere se un linguaggio è vuoto, finito o infinito; come decidere l'equivalenza di automi a stati finiti o di espressioni regolari. - 24 aprile 2013 - Lezione 7
Equivalenza e distinguibilità di stati. Minimizzazione di automi deterministici.
Automi a pila: introduzione e definizione. Configurazioni o descrizioni istantanee. Accettazione per stato finale. Accettazione per pila vuota. - 8 maggio 2013 - Lezione 8
Simulazione di automi a pila che accettano per stati finali mediante automi a pila che accettano per pila vuota. Simulazione di automi a pila che accettano per pila vuota mediante automi a pila che accettano per stati finali. Automi a pila deterministici. Determinismo e nondeterminismo: esempi di linguaggi riconosciuti da automi a pila nondeterministici ma non riconoscibili da automi a pila deterministici. - 15 maggio 2013 - Lezione 9
Grammatiche, derivazioni e linguaggi. Classificazione di Chomsky delle grammatiche e dei linguaggi. Equivalenza tra grammatiche di tipo 3 e automi a stati finiti. Equivalenza tra grammatiche di tipo 2 e automi a pila. - 22 maggio 2013 - Lezione 10
Grammatiche e linguaggi context-free: alberi sintattici e derivazioni a sinistra. Ambiguità e ambiguità inerente. Forme normali di Greibach e Chomsky. Conversione di grammatiche alla forma normale di Chomsky. Il pumping lemma per i linguaggi context-free (inizio: enunciato e un esempio). - 29 maggio 2013 - Lezione 11
Il pumping lemma per i linguaggi context-free (dimostrazione). Esempi di uso del pumping lemma. Chiusura della classe della classe dei linguaggi context-free rispetto a unione, prodotto e chiusura di Kleene. Non chiusura rispetto a intersezione e complemento. Chiusura rispetto a intersezione con linguaggi regolari. - 5 giugno 2013 - Lezione 12
Appartenenza di una stringa a un linguaggio context-free: l'algoritmo CYK. Problemi di decisione per linguaggi context-free: come decidere se un linguaggio è vuoto, finito o infinito. Cenni ad alcune prorietà non decidibili.
Codifica di stringhe mediante interi. Dimostrazione, mediante diagonalizzazione, dell'esisitenza di linguaggi non rappresentabili da grammatiche.
Link vari
Ultimo aggiornamento: 5 giugno 2013
© Giovanni
Pighizzini
Università degli Studi di
Milano