Insegnamento
AUTOMI E LINGUAGGI FORMALI
SC03100756, A.A. 2016/17

Principali informazioni sull'insegnamento
Corso di studio Corso di laurea in
INFORMATICA
SC1167, ordinamento 2011/12, A.A. 2016/17
1134838
Crediti formativi 8.0
Denominazione inglese AUTOMATA AND FORMAL LANGUAGES
Sito della struttura didattica http://informatica.scienze.unipd.it/2016/laurea
Dipartimento di riferimento Dipartimento di Matematica
Obbligo di frequenza No
Lingua di erogazione ITALIANO
Sede PADOVA

Docenti
Responsabile LAMBERTO BALLAN INF/01
Altri docenti GILBERTO FILE' INF/01

Dettaglio crediti formativi
Tipologia Ambito Disciplinare Settore Scientifico-Disciplinare Crediti
CARATTERIZZANTE Discipline Informatiche INF/01 8.0

Modalità di erogazione
Periodo di erogazione Secondo semestre
Anno di corso II Anno
Modalità di erogazione frontale

Organizzazione della didattica
Tipo ore Crediti Ore di
Corso
Ore Studio
Individuale
Turni
ESERCITAZIONE 2.0 16 34.0 Nessun turno
LEZIONE 6.0 48 102.0 Nessun turno

Calendario
Inizio attività didattiche 27/02/2017
Fine attività didattiche 09/06/2017

Commissioni d'esame
Nessuna commissione d'esame definita

Syllabus
Prerequisiti: Nozioni di logica.
Conoscenze e abilita' da acquisire: Questo corso fornisce i concetti fondamentali della teoria degli
automi e dei linguaggi formali, mostrando la loro applicazione ai compilatori.
Inoltre, introduce le nozioni di indecidibilita' e intrattabilita'.
Modalita' di esame: Scritto e orale.
Criteri di valutazione: Lo scritto contiene alcune domande che consentono di valutare il livello di apprendimento delle nozioni impartite durante il corso. Sono poi presenti esercizi di costruzione di automi e di grammatiche formali.
Contenuti: Gli argomenti principali del corso sono:

Parte 1: linguaggi regolari e analisi lessicale (3 cfu)
-- automi a stati finiti
-- espressioni e linguaggi regolari
-- analisi lessicale

Parte 2: linguaggi liberi da contesto e analisi sintattica (3 cfu)
-- grammatiche e linguaggi liberi dal contesto
-- automi a pila
-- analisi sintattica: parsers top-down (LL) e bottom-up (LR)

Parte 3: indecidibilita' e intrattabilita' (2 cfu)
-- macchine di Turing
-- concetto di indecidibilita'
-- problemi intrattabili
-- classi P e NP
Attivita' di apprendimento previste e metodologie di insegnamento: Lezioni frontali ed esercizi in classe.
Eventuali indicazioni sui materiali di studio: Vengono rese disponibili le trasparenze usate a lezione.
Testi di riferimento:
  • Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D., Automi, linguaggi e calcolabilità. Milano: Addison-Wesley Pearson Education Italia, 2003. Cerca nel catalogo
  • Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman, Compilers: Principles, Techniques, and Tools. --: Addison-Wesley, 2006. Cerca nel catalogo