Dettagli sull'Insegnamento per l'A.A. 2018/2019
Nome:
Teoria dei Linguaggi / Theory of Languages
Informazioni
Crediti:
: Master Degree in Computer Science 6 CFU (b)
: Bachelor Degree in Computer Science 6 CFU (b)
Erogazione:
Bachelor Degree in Computer Science 3rd anno curriculum General Elective
Master Degree in Computer Science 2nd anno curriculum NEDAS Elective
Master Degree in Computer Science 2nd anno curriculum SEAS Elective
Master Degree in Computer Science curriculum UBIDIS Elective
Lingua:
Italiano
Prerequisiti
Conoscenza degli argomenti trattati nei corsi base di programmazione, familiarità con strutture dati fondamentali, ricorsione e nozioni base della compilazione
Obiettivi
Profonda conoscenza della teoria dei linguaggi formali
Sillabo
- - Introduzione alla teoria dei linguaggi:
Nozioni base della teoria dei linguaggi formali.
Gerarchia di Chomsky.
- - Linguaggi regolari:
Formalismi (DFA, NFA, epsilon-NFA, espressioni regolari).
Equivalenze tra formalismi (subset construction, teorema di Kleene, algoritmo di Thompson).
Pumping Lemma e casi di studio.
Proprietà di chiusura.
Proprietà di decisione (testing emptiness, testing membership, testing equivalence).
- - Linguaggi context-free:
Formalismi (grammatiche context-free, PDA, DPDA).
Forma normale di Chomsky.
Pumping Lemma e casi di studio.
Proprietà di chiusura.
Proprietà di decisione (testing membership: algoritmo CYK).
Descrittori di Dublino
Alla fine del corso, lo studente dovrebbe
-
conoscere i principali formalismi utilizzati nella teoria degli automi e dei linguaggi formali
-
conoscere e capire le proprietà dei linguaggi regolari e dei linguaggi context free
-
avere capacità nel ragionamento formale e abilità nello sviluppare una dimostrazione
-
capire e saper spiegare specifiche di linguaggi usando notazioni formali (espressioni regolari, automi, grammatiche)
-
essere capace di leggere e capire altri testi su argomenti correlati
Testi di riferimento
- Hopcroft, Motwani, Ullman, Automi, Linguaggi e Calcolabilità , Addison-Wesley.
Modalità d'esame
Gli studenti sono incoraggiati a partecipare attivamente alle lezioni facendo domande e discutendo le soluzioni adottate negli esempi sviluppati in aula. L'esame consiste in una prova scritta sugli argomenti trattati nel corso. E' prevista anche una prova intermedia scritta che copre la prima parte del programma del corso in modo che gli studenti possano dividere il carico di studio. L'esame scritto (durata 2 ore) è costituito da un insieme di domande per la verifica delle competenze teoriche/formali e per la verifica della capacità di comprendere e risolvere esercizi significativi. Criteri di valutazione saranno: la padronanza delle nozioni e dei formalismi presentati nel corso, nonché la capacità di applicarli; la chiarezza e la completezza delle spiegazioni.
Aggiornamenti alla pagina del corso
Le informazioni sulle editioni passate di questo corso sono disponibili per i seguenti anni accademici:
Per leggere le informazioni correnti sul corso, se ancora erogato, consulta il catalogo corsi di ateneo.
Ultimo aggiornamento delle informazioni sul corso: 21 ottobre 2016, 10:35