Università degli studi dell'Insubria

AUTOMI E LINGUAGGI

A.A. di erogazione 2017/2018

Laurea triennale in INFORMATICA
 (A.A. 2015/2016)

Docenti

Anno di corso: 
3
Tipologia di insegnamento: 
Caratterizzante
Settore disciplinare: 
INFORMATICA (INF/01)
Crediti: 
6
Ciclo: 
Primo Semestre
Ore di attivita' frontale: 
48
Dettaglio ore: 
Lezione (48 ore)

Il corso, di carattere teorico, ha come obiettivo principale
l'acquisizione delle nozioni basilari su automi e linguaggi, e lo
sviluppo delle capacità di formalizzazione, astrazione, modellazione
di sistemi e analisi di problemi complessi.

Prerequisiti: 

Il corso non richiede prerequisiti. È utile comunque aver frequentato
i corsi di Algoritmi e Strutture Dati e Programmazione, ed avere
nozioni di base di Logica e di Algebra.

Automi a stati finiti determininistici (DFA), automi a stati finiti
non-deterministici (NFA) e automi a stati finiti con ε-mosse (ε-NFA):
definizione, computazione e linguaggio riconosciuto. Equivalenza fra
DFA, NFA e fra NFA ε-NFA.

Espressioni regolari. Equivalenza fra espressioni regolari e ε-NFA.

Linguaggi regolari: principali proprietà e Pumping Lemma.

Grammatiche libere dal contesto: derivazioni, alberi sintattici,
grammatiche ambigue.

Automi a pila (PDA): accettazione per stack vuoto e stato finale
(equivalenza). Equivalenza fra I linguaggi liberi dal contesto e I
linguaggi accettati da PDA.

Linguaggi liberi dal contesto: principali proprietà e Pumping Lemma.

La gerarchia di Chomsky.

Macchine di Turing deterministiche e non-deterministiche. Linguaggi
ricorsivamente enumerabili e problemi indecidibili.

48 ore di lezioni frontali, 102 ore di studio individuale.

Modalita' di verifica dell'apprendimento: 

L’esame consiste in un colloquio orale teso all'accertamento
dell'acquisizione e della corretta comprensione degli argomenti
presentati a lezione.

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Automi, linguaggi e calcolabilità, Pearson Paravia Bruno Mondadori, Terza Edizione, 2009.

Ricevimento studenti: su appuntamento tramite richiesta via e-mail.

Cerchi il programma? Potrebbe non essere ancora stato caricato o riferirsi ad insegnamenti che verranno erogati in futuro.
Seleziona l‘anno in cui ti sei immatricolato e troverai le informazioni relative all'insegnamento del tuo piano di studio.

A.A. 2019/2020

Anno di corso: 3
Curriculum: PERCORSO COMUNE

A.A. 2018/2019

Anno di corso: 3
Curriculum: PERCORSO COMUNE

A.A. 2017/2018

Anno di corso: 3
Curriculum: PERCORSO COMUNE

A.A. 2016/2017

Anno di corso: 3
Curriculum: PERCORSO COMUNE

A.A. 2014/2015

Anno di corso: 3
Curriculum: PERCORSO COMUNE

A.A. 2013/2014

Anno di corso: 3
Curriculum: PERCORSO COMUNE