Linguaggi e grammatiche; insiemi regolari; grammatiche context-free; forme normali di Chomsky e di Greibach. Automi a stati finiti e linguaggi regolari; pumping lemma per linguaggi regolari e linguaggi context-free; proprietà dei linguaggi context-free. Gerarchia di Chomsky; macchine di Turing. Codici e sottomonoidi; test per codici; misura di un codice; insiemi completi; composizione. Codici prefissi, codici prefissi massimali; operazioni su codici prefissi.
- Thomas A. Sudkamp
Languages and Machines
Addison-Wesley, 1997
- G. Ausiello, F. D'Amore, G. Gambosi
Linguaggi Modelli Complessità
Franco Angeli, 2003
- Jean Berstel, Dominique Perrin
Theory of Codes
Academic Press, 1985
Obiettivi Formativi
Conoscenze:
Proprietà dei linguaggi formali, relazioni con grammatiche e automi; caratteristiche e proprietà dei codici e dei codici prefissi.
Competenze acquisite:
competenze nella teoria dei linguaggi formali in relazione con grammatiche e automi, e nella teoria dei codici.
Capacità acquisite (al termine del corso):
Al termine del corso gli studenti dovrebbero aver acquisito la capacità di affrontare e risolvere problemi relativi ai linguaggi, alla definizione di grammatiche e alla progettazione di automi. Inoltre dovrebbero essere in grado di utilizzare la teoria dei codici per definire ed analizzare codici e codici prefissi.
Linguaggi e grammatiche: insiemi regolari; grammatiche regolari; grammatiche context-free; derivazioni e ambiguità; analisi sintattica; forme normale di Chomsky e di Greibach.
Automi a stati finiti e linguaggi regolari: automi a stati finiti deterministici e non deterministici; pumping lemma per linguaggi regolari; proprietà dei linguaggi regolari.
Automi a pila e linguaggi context-free: automi a pila e linguaggi context-free; pumping lemma per linguaggi context-free; proprietà dei linguaggi context-free.
Gerarchia di Chomsky: linguaggi contestuali, ricorsivi e ricorsivamente enumerabili; macchine di Turing.
Codici: codici e sottomonoidi; test per codici; misura di un codice; insiemi completi; composizione.
Codici prefissi: automa di un codice prefisso; codici prefissi massimali; operazioni su codici prefissi; codici semaforo; codici sincroni; lunghezza media.