Linguaggi e Logiche per L'Informatica

Scopo del corso è l'acquisizione delle nozioni fondamentali della teoria dei linguaggi formali e della logica proposizionale.  

  • N. ore di didattica assistita: 32 ore di lezioni + 24 ore di esercitazioni
  • SSD: INF/01 - informatica

Modalità di Esame

L'esame consta di una prova scritta. La prova orale è facoltativa.  

Programma del Corso

  • Linguaggi e Grammatiche: Linguaggi. Grammatiche. Concetto di derivazione.
  • Linguaggi Regolari e Analizzatori Lessicali: Grammatiche di tipo 3 e linguaggi regolari. Espressioni regolari. Automi deterministici e non, eliminazione del non-determinismo. Esempi di scrittura di analizzatori lessicali.
  • Linguaggi Non Contestuali e Automi a Pila: Alberi di parsing. Derivazioni. Automi a pila deterministici e non. Analisi sintattica di tipo ascendente o discendente.
  • Logica Proposizionale: Sintassi. Semantica. Tabbelle di verità. Metodo dei tableux. 

Riferimenti

  • F. Pirri, L.C. Aiello, Strutture, logica, linguaggi, Pearson
  • J. E. Hopcroft, R. Motwani, J. D. Ullman, Automi, linguaggi e calcolabilità, Addison Wesley
  • G. Ausiello, F. D'Amore, G. Gambosi, Linguaggi, Modelli Complessità, Disponibile elettronicamente sul sito del corso di informatica teorica del Prof. Ausiello. 

Ricevimento

Il docente riceve il Mercoledì dalle ore 11:30 alle ore 13:30.