Dettagli sull'Insegnamento per l'A.A. 2018/2019

Le informazioni che state leggendo si riferiscono all'anno accademico 2018/2019. Per questo molti collegamenti non sono disponibili e i dati potrebbero essere incompleti. Per leggere le informazioni correnti sul corso, se ancora erogato, consulta il catalogo corsi di ateneo. Per consultare le informazioni relative ad altri anni accademici, usa la lista in fondo a questa pagina.

A. Accademico:

2018/2019

Nome:

Teoria dei Linguaggi / Theory of Languages

Tipo:

Corso singolo

Informazioni

Codice:

DT0269

SSD:

INF/01

Crediti:

: Master Degree in Computer Science 6 CFU (b)
: Bachelor Degree in Computer Science 6 CFU (b)

Periodo:

2^nd semester

Erogazione:

Bachelor Degree in Computer Science 3^rd anno curriculum General Elective
Master Degree in Computer Science 2^nd anno curriculum NEDAS Elective
Master Degree in Computer Science 2^nd anno curriculum SEAS Elective
Master Degree in Computer Science curriculum UBIDIS Elective

Lingua:

Italiano

Docenti:

Sergio Orefice

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.

Risorse Internet

Homepage:

http://www.di.univaq.it/orefice/corsi.html

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