Home » Archivo » Archvio 2013 » AUTOMI E LINGUAGGI FORMALI - 2013/2014

Laurea in Informatica

Salta il menu di secondo livello

AUTOMI E LINGUAGGI FORMALI - 8 CFU - A.A. 2013/2014

Sito per la parte di automi e linguaggi formali

Insegnante

Prof.ssa Francesca Rossi

Periodo

II Anno - 1 Trimestre | 01/10/2013 - 07/12/2013

Ore: 64 (16 esercitazione, 48 lezione)

Torna su ▲

Prerequisiti

Nozioni di logica.

Conoscenze e abilità 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'.

Modalità 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

Attività 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

Torna su ▲