Automi, linguaggi e calcolabilità
Pearson Education, 2009
Indice e argomenti trattati
Avvisi
Informazioni generali
Materiale di riferimento
Argomenti delle lezioni svolte
Link vari
Testo consigliato:
|
|
J.E. Hocroft, R. Motwani, J.D. Ullman Automi, linguaggi e calcolabilità Pearson Education, 2009 Indice e argomenti trattati
|
Esercizi:
Esercizi vari, molti dei quali
svolti a lezione, in aggiunta a quelli presenti sul libro di testo.
Argomenti delle lezioni svolte
Link vari
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.
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.
Trasformazione di automi nondeterministici in automi
deterministici: la costruzione per sottoinsiemi.
Equivalenza tra automi a stati finiti deterministici
e nondeterministici (conclusione). Automi con epsilon-mosse.
Trasformazione di automi con epsilon-mosse in automi
nondeterministici.
Operazioni su linguaggi: operazioni insiemistiche
(unione, intersezione, complemento),
prodotto o concatenazione, potenza, chiusura di
Kleene, chiusura positiva.
Le espressioni regolari. Esempi.
La classe dei linguaggi regolari.
Il teorema di Kleene: dalle espressioni
regolari agli automi a stati finiti.
Il teorema di Kleene: dagli automi a stati finiti
alle espressioni regolari. Esempi.
Il pumping lemma per i linguaggi regolari.
Esempi di dimostrazioni di non regolarità
mediante il pumping lemma.
Pumping lemma per i linguaggi regolari: ulteriori esempi.
Chiusura della classe dei linguaggi regolari rispetto
a complemento, intersezione, differenza.
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.
Equivalenza e distinguibilità di stati.
Minimizzazione di automi deterministici.
Automi a pila: introduzione e definizione.
Configurazioni o descrizioni istantanee.
Accettazione per stati finali.
Accettazione per pila vuota.
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.
Grammatiche, derivazioni e linguaggi.
Classificazione di Chomsky delle grammatiche
e dei linguaggi.
Equivalenza tra grammatiche di tipo 3 e automi
a stati finiti.
Grammatiche e linguaggi context-free:
alberi sintattici e derivazioni a sinistra.
Ambiguità e ambiguità inerente.
Equivalenza tra grammatiche di tipo 2 e automi a
pila: trasformazione di grammatiche in automi a pila;
trasformazione di automi a pila in grammatiche.
Forme normali di Greibach e Chomsky.
Conversione di grammatiche context-free alla forma normale
di Chomsky.
Il pumping lemma per i linguaggi context-free.
Esempi.
Il pumping lemma per i linguaggi context-free (revisione).
Esempi.
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.
Esempio di grammatica context-free per un frammento del
linguaggio Java.
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 proprietà non decidibili per i linguaggi
context-free
(universalità, equivalenza, equivalenza con linguaggio regolare,
regolarità).
Introduzione alle macchine di Turing.
Macchina a un nasto come riconoscitore.
Varianti: macchine a più nastri, macchine
con nastro infinito da entrambi i lati. Esempi.
Determinismo e nondeterminismo.
Simulazione di macchine nondeterministiche mediante
macchine deterministiche,
Macchine con output.
La macchina di Turing universale.
Codifiche mediante interi.
Esempi di dimostrazioni per diagonalizzazione.
Esistenza di un linguaggio non di tipo 0.
Macchine di Turing e programmi. Tesi di Church.
Funzioni ricorsive (o calcolabili). Esistenza di una
funzione non ricorsiva.
Insiemi ricorsivi (o decidibili). Insiemi ricorsivamente numerabili
(o semidecidibili). Esistenza di un insieme ricorsivamente
numerabile ma non ricorsivo: il problema dell'arresto.
Complemento di insiemi ricorsivamente numerabili.
Linguaggi di tipo 0 e insiemi ricorsivamente numerabili.
Gerarchia di Chomsky e decidibilità.
| Ultimo aggiornamento: 30 gennaio 2017 © Giovanni Pighizzini Università degli Studi di Milano |