Teoria dei Linguaggi
Anno Accademico 2018/2019
Corso di Laurea Magistrale in Informatica
In questa pagina potete trovare
Avvisi e informazioni generali
Pagine anni precedenti
Avvisi e informazioni generali
- 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.
-
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.
- Informazioni su esami 2018/2019
È
disponibile un documento contenente le
informazioni relative ai contenuti e alle modalità della prova
d'esame, con un elenco di alcuni approfondimenti proposti.
Argomenti delle lezioni
- 27 febbraio 2019 - Lezione 1
Presentazione del corso.
Richiami di nozioni fondamentali relative ad alfabeti, stringhe,
linguaggi.
Il problema della rappresentazione di linguaggi.
- 1º marzo 2019 - Lezione 2
Richiami su 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.
- 6 marzo 2019 - Lezione 3
Richiami su operazioni fondamentali su linguaggi (operazioni
insiemistiche, prodotto o concatenazione, chiusura di Kleene,
chiusura positiva) e su espressioni regolari.
Trasformazione di automi nondeterministici in automi deterministici
(costruzione per sottoinsiemi).
Ottimalità della costruzione per sottoinsiemi rispetto al
numero di stati: un esempio di caso "peggiore".
Automi nondeterministici con stati iniziali multipli e con
epsilon-transizioni.
- 13 marzo 2019 - Lezione 4
Un criterio per stabilire
limiti inferiori per il numero di stati degli automi nondeterministici:
fooling set ed extended fooling set.
- 15 marzo 2019 - Lezione 5
Complessità in stati (state complexity e nondeterministic state
complexity). Complessità del complemento, unione, intersezione,
prodotto.
- 20 marzo 2019 - Lezione 6
Operazioni su linguaggi e complessità in stati:
star, reversal, shuffle, quoziente, morfismo.
- 22 marzo 2019 - Lezione 7
Operazioni su linguaggi:
sostituzione, morfismo inverso. Altri esempi di operazioni e
costruzioni corrispondenti su automi.
- 27 marzo 2019 - Lezione 8
Relazioni di equivalenza ed automi. Relazioni di Myhill-Nerode
associata a un linguaggio. Il teorema di Myhill-Nerode e il teorema
dell'automa minimo.
Cenni al problema della minimizzazione nel caso di automi
nondeterministici.
- 29 marzo 2019 - Lezione 9
Minimizzazione di automi: l'algoritmo di Brzozowski.
Rappresentazione di automi mediante matrici.
Calcolo del numero di stringhe di una data lunghezza accettate
da un automa. Esempi.
- 3 aprile 2019 - Lezione 10
Rappresentazione di automi nondeterministici mediante matrici.
Calcolo del numero di cammini accettanti.
Automi pesati.
Automi probabilistici.
Evento associato ad un automa probabilistico.
Linguaggio accettato con una certa soglia.
Soglia isolata.
Il teorema di Rabin per gli automi probabilistici.
- 5 aprile 2019 - Lezione 11
Automi two-way: introduzione ed esempi.
Simulazione di automi two-way mediante automi one-way.
- 10 aprile 2019 - Lezione 12
Il problema di Sakoda e Sipser.
Richiami sul pumping lemma per i linguaggi regolari.
Grammatiche. Esempi.
Alcuni esercizi relativi ai linguaggi
regolari
- 12 aprile 2019 - Lezione 13
Gerarchia di Chosmky.
Equivalenza tra grammatiche di tipo 3 e automi a stati finiti.
Decidibilità dei linguaggi dipendenti dal contesto.
Semidecidibilità dei linguaggi di tipo 0.
Automi a pila: definizione.
- 17 aprile 2019 - Lezione 14
Automi a pila.
Determinismo e nondeterminismo.
Accettazione a pila vuota e per stati finali e loro equivalenza
del caso degl automi a pila nondeterministici.
- 3 maggio 2019 - Lezione 15
Equivalenza tra grammatiche libere dal contesto e automi a pila.
- 8 maggio 2019 - Lezione 16
Forme normali di Greibach e di Chomsky per il linguaggi liberi dal
contesto. Trasformazione in forma normale di Chomsky di grammatiche
libere dal contesto.
Il pumping lemma per i linguaggi liberi dal contesto. Esempi.
- 10 maggio 2019 - Lezione 17
Il lemma di Ogden. Esempi.
- 15 maggio 2019 - Lezione 18
Ambiguità e ambiguità inerente.
Esistenza di linguaggi liberi dal contesto inerentemente ambigui.
Chiusura della classe dei linguaggi context-free rispetto a
unione, prodotto, chiusura di Kleene, intersezione con linguaggi regolari.
Non chiusura rispetto a intersezione, complemento, shuffle.
- 17 maggio 2019 - Lezione 19
Chiusura della classe dei linguaggi context-free rispetto a
morfismo, sostituzione, morfismo inverso.
Automi a pila deterministici. Differenza tra accettazione per pila
vuota e per stati finali. Linguaggi context-free deterministici.
Proprietà di chiusura della classe dei linguaggi context-free
deterministici: non chiusura
rispetto a unione e intersezione; chiusura rispetto a unione e
intersezione con linguaggi regolari; chiusura rispetto a complemento
(dimostrazione nella lezione successiva); non chiusura rispetto a
morfismo, prodotto, star, reversal; non chiusura rispetto al prodotto
a sinistra con linguaggi finiti; chiusura rispetto al prodotto a destra
con linguaggi regolari.
- 22 maggio 2019 - Lezione 20
Chiusura della classe dei linguaggi context-free deterministici
rispetto al complemento: transformazione di un automa a pila
deterministico in un automa a pila deterministico per il complemento.
Come dimostrare che un linguaggio context-free non è
deterministico. Esempi.
- 24 maggio 2019 - Lezione 21
Un criterio basato sull'equivalenza di Myhill-Nerode per dimostrare
che un linguaggio linguaggio context-free non è
deterministico.
Il teorema di Chomsky-Schützenberger per i linguaggi
context-free (enunciato ed esempi).
Regolarità dei linguaggi context-free su alfabeti di una
lettera. Cenni alla struttura degli automi unari.
- 29 maggio 2019 - Lezione 22
Il teorema di Parikh (enunciato e esempi).
Grammatiche self-embedding. Regolarità dei linguaggi generati
da grammatiche non self-embedding.
Alcuni esercizi
- 31 maggio 2019 - Lezione 23
Automi a pila two-way: esempi di riconoscimento di linguaggi non
context-free.
Esempi di macchine di Turing e automi limitati linearmente (automi
linear bounded).
Problemi di decisione per linguaggi regolari (vuotezza, finitezza,
universalità, equivalenza).
- 5 giugno 2019 - Lezione 24
Il linguaggio delle computazioni valide di una macchina di Turing
e il suo complemento.
Problemi di decisione per linguaggi context-free:
decidibilità di vuotezza e finitezza; indecidibilità
di universalità, equivalenza, equivalenza con regolare;
decidibilità di queste proprietà nel caso dei
linguaggi context-free deterministici.
Discussione delle modalità d'esame.
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à).