Teoria dei Linguaggi
Anno Accademico 2015/2016
Corso di Laurea Magistrale in Informatica - Milano
In questa pagina potete trovare
Avvisi e informazioni generali
Argomenti delle lezioni
Bibliografia di riferimento
Avvisi e informazioni generali
- Informazioni su esami
È
disponibile un documento contenente le
informazioni relative ai contenuti e alle modalità della prova
d'esame, con un elenco di alcuni approfondimenti proposti.
-
Il corso è previsto come complementare dal manifesto degli studi
della Laurea Magistrale in Informatica.
Gli studenti dei corsi di laurea triennali possono inserire
il corso nel proprio piano di studi tra i crediti a scelta libera.
-
Il corso si tiene per la prima volta nell'anno accademico 2015/2016, secondo semestre, a partire dal 3 di marzo, con
il seguente orario:
giovedì e venerdì 8.30-10.30, via Comelico 39,
aula 5. Da metà aprile la lezione del venerdì è spostata al martedì nello
stesso orario (aula 5, tranne nei giorni 19 e 26 aprile, 3 e 24 maggio in
cui si terrà in aula 6).
L'attivazione del corso è prevista ad anni alterni.
- È necessaria una buona conoscenza dei contenuti del corso di
Linguaggi Formali e Automi.
- Il corso riguarda la teoria dei linguaggi formali e degli automi
(in senso ampio, come dispositivi di calcolo di vario tipo per riconoscere
linguaggi o calcolare funzioni, dunque non solo automi a stati finiti, ma
diversi tipi di modelli).
Verranno ripresi ed approfonditi alcuni contenuti del corso di Linguaggi
Formali e Automi, integrati con nuovi argomenti.
Si porrà particolare attenzione allo studio delle risorse
computazionali utilizzate dai differenti modelli per il riconoscimento delle diverse classi di linguaggi.
Saranno illustrati alcuni sviluppi recenti ottenuti nelle ricerche nel settore,
nonché alcuni problemi aperti.
Un elenco dettagliato degli argomenti trattati sarà pubblicato su
questa pagina.
Argomenti delle lezioni
- 3 marzo 2016 - Lezione 1
Presentazione del corso.
Richiami di nozioni fondamentali relative ad alfabeti, stringhe,
linguaggi.
- 4 marzo 2016 - Lezione 2
Automi a stati finiti deterministici e nondeterministici.
Distinguibilità di stringhe. Un criterio per stabilire un
limite inferiore per il numero di stati degli automi deterministici.
- 10 marzo 2016 - Lezione 3
Trasformazione di automi nondeterministici in automi deterministici
e sua ottimailtà in termini di stati.
Un criterio per stabilire
limiti inferiori per il numero di stati degli automi nondeterministici:
la tecnica del fooling set.
- 11 marzo 2016 - Lezione 4
Complessità in stati (state complexity e nondeterministic state
complexity). Complessità del complemento, unione, intersezione,
prodotto di linguaggi.
- 7 aprile 2016 - Lezione 5
Operazioni sui linguaggi: star, reversal, shuffle, quoziente,
morfismo, sostituzione, morfismo inverso.
- 8 aprile 2016 - Lezione 6
Relazioni di equivalenza ed automi. Relazioni di Myhill-Nerode
associata a un linguaggio. Il teorema di Myhill-Nerode e il teorema
dell'automa minimo.
Alcuni esercizi
- 19 aprile 2016 - Lezione 7
Minimizzazione di automi: l'algoritmo di Brzozowski.
Automi two-way: definizione ed esempi.
- 21 aprile 2016 - Lezione 8
Simulazione di automi two-way mediante automi one-way.
Il problema di Sakoda e Sipser.
- 26 aprile 2016 - Lezione 9
Rappresentazione di automi mediante matrici.
Cenni agli automi pesati e agli automi probabilistici.
- 28 aprile 2016 - Lezione 10
Richiami sul pumping lemma per i linguaggi regolari.
Linguaggi regolari nel caso di alfabeto di una lettera.
Automi deterministici unari e insiemi definitivamente periodici.
Automi nondeterministici unari. Forma normale di Chrobak per
gli automi nondeterministici unari. Conversione di automi
nondeterministici unari in automi deterministici.
- 3 maggio 2016 - Lezione 11
Grammatiche libere dal contesto: richiami ed esempi.
Automi a pila. Accettazione per stati finali e per pila vuota.
- 5 maggio 2016 - Lezione 12
Una forma normale per gli automi a pila.
Equivalenza tra grammatiche libere dal contesto e automi a pila.
- 10 maggio 2016 - Lezione 13
Il pumping lemma per i linguaggi liberi dal contesto. Esempi.
- 12 maggio 2016 - Lezione 14
Il lemma di Ogden. Esempi.
Esistenza di linguaggi liberi dal contesto inerentemente ambigui.
- 17 maggio 2016 - Lezione 15
Regolarità dei linguaggi context-free unari.
Insiemi semilineari. La mappa di Parikh e il teorema di Parikh
(enunciato). Esempi.
Grammatiche self-embedding. Regolarità dei linguaggi generati
da grammatiche non self-embedding.
- 19 maggio 2016 - Lezione 16
Chiusura della classe dei linguaggi context-free rispetto a
operazioni regolari, intersezione con linguaggi regolari, reversal,
morfismo, sostituzione con linguaggi context-free, morfismo inverso.
Non chiusura rispetto a intersezione, complemento, shuffle.
- 24 maggio 2016 - Lezione 17
Automi a pila deterministici. Differenza tra accettazione per pila
vuota e per stati finali. Linguaggi context-free deterministici.
Chiusura della classe dei linguaggi context- free deterministici
rispetto al complemento.
- 26 maggio 2016 - Lezione 18
Non chiusura della classe dei linguaggi context-free deterministici
unione, intersezione, prodotto, start, reversal, morfismo,
sostituzione.
Cenni agli automi limited e alla loro potenza computazionale.
Alcuni esercizi
- 31 maggio 2016 - Lezione 19
Il teorema di Chomsky-Schützenberger per i linguaggi
context-free. Esempi. Automi a pila two-way: esempi.
Esempi di macchine di Turing e automi linear bounded.
Decidibilità dei linguaggi dipendenti dal contesto.
- 7 giugno 2016 - Lezione 20
Semidecidibilità dei linguaggi di tipo 0. Esempi.
Bibliografia di riferimento
Gli argomenti trattati nel corso possono essere reperiti su vari testi.
Segue un elenco dei principali. Indicazioni più dettagliate
verranno fornite man mano durante lo svolgimento del corso.
- J. Shallit
A Second Course
in Formal Languages and Automata Theory
Cambridge University Press, 2009
- J. Hopcroft and J. Ullman
Introduction to Automata Theory, Languages, and Computation
Addison-Wesley, 1979
Nota: nelle edizioni successive (2000, 2006, ed. italiana
2009), più orientate a corsi di base, molti argomenti sono stati
eliminati o sono trattati superficialmente.
- J. Hopcroft and J. Ullman
Formal languages and their relation to automata
Addison Wesley, 1969
Nota: ``Precursore'' del libro del 1979. Ben scritto, ma poco
aggiornato su alcuni argomenti.
Scaricabile dalla ACM
Digital Library (dalla rete all'interno dell'università).